<!DOCTYPE HTML>
<html lang="zh-CN">


<head>
    <meta charset="utf-8">
    <meta name="keywords" content="Parallel Sort, python,machine learning,deep learning,html,css,c,c++,cpp,cmake,ros,linux,ubuntu">
    <meta name="description" content="本文描述了Paralle Sort">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="referrer" content="no-referrer-when-downgrade">
    <!-- Global site tag (gtag.js) - Google Analytics -->


    <title>Parallel Sort | JackWang&#39;s Blog</title>
    <link rel="icon" type="image/png" href="/favicon.png">

    <link rel="stylesheet" type="text/css" href="/libs/awesome/css/all.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/materialize/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/css/my.css">

    <script src="/libs/jquery/jquery-3.6.0.min.js"></script>

<meta name="generator" content="Hexo 5.4.2">
<style>.github-emoji { position: relative; display: inline-block; width: 1.2em; min-height: 1.2em; overflow: hidden; vertical-align: top; color: transparent; }  .github-emoji > span { position: relative; z-index: 10; }  .github-emoji img, .github-emoji .fancybox { margin: 0 !important; padding: 0 !important; border: none !important; outline: none !important; text-decoration: none !important; user-select: none !important; cursor: auto !important; }  .github-emoji img { height: 1.2em !important; width: 1.2em !important; position: absolute !important; left: 50% !important; top: 50% !important; transform: translate(-50%, -50%) !important; user-select: none !important; cursor: auto !important; } .github-emoji-fallback { color: inherit; } .github-emoji-fallback img { opacity: 0 !important; }</style>
<link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css">
<link rel="stylesheet" href="/css/prism-line-numbers.css" type="text/css"></head>



   <style>
    body{
       background-image: url(https://cdn.jsdelivr.net/gh/Tokisaki-Galaxy/res/site/medias/background.jpg);
       background-repeat:no-repeat;
       background-size: 100% 100%;
       background-attachment:fixed;
    }
</style>



<body>
    <header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="/" class="waves-effect waves-light">
                    
                    <img src="/medias/logo.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">JackWang&#39;s Blog</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fas fa-bars"></i></a>
<ul class="right nav-menu">
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/" class="waves-effect waves-light">
      
      <i class="fas fa-home" style="zoom: 0.6;"></i>
      
      <span>首页</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="" class="waves-effect waves-light">

      
      <i class="fas fa-book-reader" style="zoom: 0.6;"></i>
      
      <span>博客</span>
      <i class="fas fa-chevron-down" aria-hidden="true" style="zoom: 0.6;"></i>
    </a>
    <ul class="sub-nav menus_item_child ">
      
      <li>
        <a href="/tags">
          
          <i class="fas fa-tags" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按标签归类文章</span>
        </a>
      </li>
      
      <li>
        <a href="/categories">
          
          <i class="fas fa-bookmark" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按目录归类文章</span>
        </a>
      </li>
      
      <li>
        <a href="/archives">
          
          <i class="fas fa-archive" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按日期分类文章</span>
        </a>
      </li>
      
    </ul>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/about" class="waves-effect waves-light">
      
      <i class="fas fa-user-circle" style="zoom: 0.6;"></i>
      
      <span>关于</span>
    </a>
    
  </li>
  
  <li>
    <a href="#searchModal" class="modal-trigger waves-effect waves-light">
      <i id="searchIcon" class="fas fa-search" title="搜索" style="zoom: 0.85;"></i>
    </a>
  </li>
</ul>



<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="/medias/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">JackWang&#39;s Blog</div>
        <div class="logo-desc">
            
            JackWang的个人博客
            
        </div>
    </div>

    <ul class="menu-list mobile-menu-list">
        
        <li class="m-nav-item">
	  
		<a href="/" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-home"></i>
			
			首页
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="javascript:;">
			
				<i class="fa-fw fas fa-book-reader"></i>
			
			博客
			<span class="m-icon"><i class="fas fa-chevron-right"></i></span>
		</a>
            <ul  style="background:  ;" >
              
                <li>

                  <a href="/tags " style="margin-left:75px">
				  
				   <i class="fa fas fa-tags" style="position: absolute;left:50px" ></i>
			      
                              <span>按标签归类文章</    span>

                  </a>
                </li>
              
                <li>

                  <a href="/categories " style="margin-left:75px">
				  
				   <i class="fa fas fa-bookmark" style="position: absolute;left:50px" ></i>
			      
                              <span>按目录归类文章</    span>

                  </a>
                </li>
              
                <li>

                  <a href="/archives " style="margin-left:75px">
				  
				   <i class="fa fas fa-archive" style="position: absolute;left:50px" ></i>
			      
                              <span>按日期分类文章</    span>

                  </a>
                </li>
              
            </ul>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/about" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-user-circle"></i>
			
			关于
		</a>
          
        </li>
        
        
    </ul>
</div>


        </div>

        
    </nav>

</header>

    
<script src="/libs/cryptojs/crypto-js.min.js"></script>
<script>
    (function() {
        let pwd = '';
        if (pwd && pwd.length > 0) {
            if (pwd !== CryptoJS.SHA256(prompt('抱歉，这篇文章并不想让所有人都看到，请输入授权密码观看')).toString(CryptoJS.enc.Hex)) {
                alert('密码错误，将返回主页！');
                location.href = '/';
            }
        }
    })();
</script>




<div class="bg-cover pd-header post-cover" style="background-image: url('https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221108225726700.png')">
    <div class="container" style="right: 0px;left: 0px;">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <h1 class="description center-align post-title">Parallel Sort</h1>
                </div>
            </div>
        </div>
    </div>
</div>




<main class="post-container content">

    
    <link rel="stylesheet" href="/libs/tocbot/tocbot.css">
<style>
    #articleContent h1::before,
    #articleContent h2::before,
    #articleContent h3::before,
    #articleContent h4::before,
    #articleContent h5::before,
    #articleContent h6::before {
        display: block;
        content: " ";
        height: 100px;
        margin-top: -100px;
        visibility: hidden;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        width: 345px;
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        padding: 35px 0 15px 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content {
        padding-bottom: 30px;
        overflow: auto;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;

        position: absolute;
        right: 23.5vw;
        display: block;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #floating-toc-btn {
        position: fixed;
        right: 15px;
        bottom: 76px;
        padding-top: 15px;
        margin-bottom: 0;
        z-index: 998;
    }

    #floating-toc-btn .btn-floating {
        width: 48px;
        height: 48px;
    }

    #floating-toc-btn .btn-floating i {
        line-height: 48px;
        font-size: 1.4rem;
    }
</style>
<div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                            <a href="/tags/C%E8%AF%AD%E8%A8%80/">
                                <span class="chip bg-color">C语言</span>
                            </a>
                        
                            <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/">
                                <span class="chip bg-color">数据结构和算法</span>
                            </a>
                        
                            <a href="/tags/%E5%A4%9A%E7%BA%BF%E7%A8%8B/">
                                <span class="chip bg-color">多线程</span>
                            </a>
                        
                            <a href="/tags/%E5%90%8C%E6%AD%A5%E4%B8%8E%E4%BA%92%E6%96%A5/">
                                <span class="chip bg-color">同步与互斥</span>
                            </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                    <div class="post-cate">
                        <i class="fas fa-bookmark fa-fw icon-category"></i>
                        
                            <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/" class="post-category">
                                数据结构和算法
                            </a>
                        
                    </div>
                    
                </div>
            </div>

            <div class="post-info">
                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-minus fa-fw"></i>发布日期:&nbsp;&nbsp;
                    2022-11-08
                </div>
                

                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-check fa-fw"></i>更新日期:&nbsp;&nbsp;
                    2023-06-01
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-file-word fa-fw"></i>文章字数:&nbsp;&nbsp;
                    8.9k
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-clock fa-fw"></i>阅读时长:&nbsp;&nbsp;
                    40 分
                </div>
                

                
                    <div id="busuanzi_container_page_pv" class="info-break-policy">
                        <i class="far fa-eye fa-fw"></i>阅读次数:&nbsp;&nbsp;
                        <span id="busuanzi_value_page_pv"></span>
                    </div>
				
            </div>
        </div>
        <hr class="clearfix">

        

        

        <div class="card-content article-card-content">
            <div id="articleContent">
                <p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/%E5%B1%8F%E5%B9%95%E5%BD%95%E5%88%B62022-11-14-%E4%B8%8A%E5%8D%882.31.43.gif" alt="Parallel Sort"></p>
<h2 id="Parallel-Sort"><a href="#Parallel-Sort" class="headerlink" title="Parallel Sort"></a>Parallel Sort</h2><p>最近在CS537这门课程上学习了<code>Mutex</code>、<code>Conditional Variable (CV)</code>、<code>Semaphore</code>等等用于线程同步与互斥的量。</p>
<p>当然，光说不练假把式。作为练习，写了一个多线程排序的项目出来。</p>
<p>个人觉得，这个项目对多线程编程能力有很大的提升，尤其是死锁的DEBUG，所以特地把这个项目记录一下。</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221108225726700.png" alt="Parallel Sort"></p>
<h2 id="项目说明"><a href="#项目说明" class="headerlink" title="项目说明"></a>项目说明</h2><p>本项目要求对一个包含多个记录（<code>record</code>）的二进制文件进行排序。二进制文件中，每一个记录（<code>record</code>）占100个字节。前4个字节作为该记录的键（<code>key</code>），后6个字节作为该记录的值（<code>value</code>）。</p>
<p>项目要求对所有的记录，按照其键的值进行排序，并将排序后的结果写入到新的二进制文件中。</p>
<p>生成待排序二进制文件的代码如下：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">&lt;fcntl.h></span></span>
<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">&lt;assert.h></span></span>
<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">&lt;stdio.h></span></span>
<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">&lt;stdlib.h></span></span>
<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">&lt;unistd.h></span></span>

<span class="token keyword">typedef</span> <span class="token keyword">struct</span> rec <span class="token punctuation">{</span>
    <span class="token keyword">int</span> key<span class="token punctuation">;</span>
    <span class="token keyword">int</span> value<span class="token punctuation">[</span><span class="token number">24</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// 96 bytes</span>
<span class="token punctuation">}</span> rec_t<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token keyword">int</span> argc<span class="token punctuation">,</span> <span class="token keyword">char</span> <span class="token operator">*</span>argv<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>argc <span class="token operator">!=</span> <span class="token number">3</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">fprintf</span><span class="token punctuation">(</span><span class="token constant">stderr</span><span class="token punctuation">,</span> <span class="token string">"generate numkeys file\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">exit</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">int</span> n <span class="token operator">=</span> <span class="token function">atoi</span><span class="token punctuation">(</span>argv<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">char</span> <span class="token operator">*</span>file <span class="token operator">=</span> argv<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> fd <span class="token operator">=</span> <span class="token function">open</span><span class="token punctuation">(</span>file<span class="token punctuation">,</span> O_CREAT <span class="token operator">|</span> O_WRONLY <span class="token operator">|</span> O_TRUNC<span class="token punctuation">,</span> <span class="token number">0666</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>fd <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">perror</span><span class="token punctuation">(</span><span class="token string">"open"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">exit</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">int</span> k<span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span>k <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> k <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> k<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">long</span> u <span class="token operator">=</span> <span class="token function">random</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        rec_t r<span class="token punctuation">;</span>
        r<span class="token punctuation">.</span>key <span class="token operator">=</span> u<span class="token punctuation">;</span>
        <span class="token keyword">int</span> i<span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">24</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            r<span class="token punctuation">.</span>value<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">random</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">int</span> rc <span class="token operator">=</span> <span class="token function">write</span><span class="token punctuation">(</span>fd<span class="token punctuation">,</span> <span class="token operator">&amp;</span>r<span class="token punctuation">,</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span>rec_t<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">assert</span><span class="token punctuation">(</span>rc <span class="token operator">==</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span>rec_t<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token function">close</span><span class="token punctuation">(</span>fd<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="代码说明"><a href="#代码说明" class="headerlink" title="代码说明"></a>代码说明</h2><blockquote>
<p>架构决定性能</p>
</blockquote>
<p><strong>本项目的模型以<code>sort_job</code>为核心，采用多个排序线程、多个合并线程的方式，本质上是生产者——消费者模型。</strong></p>
<p>具体来说，程序将需要排序的文件分成多个小块，将其抽象为<code>sort_job</code>，而后每个排序线程<code>sort_worker</code>认领一个<code>sort_job</code>，每个<code>sort_worker</code>对认领到的<code>sort_job</code>进行排序。在排序完成后，<code>sort_worker</code>将排序完成的<code>sort_job</code>（称为<code>sorted_job</code>，本质上就是<code>sort_job</code>）放入到由<code>sorted_job</code>组成的的队列<code>sorted_jobs</code>中。</p>
<p>而后排序线程<code>merge_worker</code>从<code>sorted_jobs</code>队列中取出两个<code>sorted_job</code>，将他们合并，得到一个新的，包含记录数量更多的<code>sorted_job</code>，并将该<code>sorted_job</code>插入到<code>sorted_jobs</code>队列中。</p>
<p><code>merge_worker</code>不断地进行合并，直到<code>sorted_jobs</code>队列最后仅剩余一个<code>sorted_job</code>，且该<code>sorted_job</code>中的记录数量等于总记录数量，则此时排序结束，将排序后的记录写入到文件中。</p>
<h3 id="1-byte-t、byteStream-t、record-t类型"><a href="#1-byte-t、byteStream-t、record-t类型" class="headerlink" title="1. byte_t、byteStream_t、record_t类型"></a>1. byte_t、byteStream_t、record_t类型</h3><p>项目中一个记录是100个字节，然而从文件中读取出所有记录之后，如果在比较得时候，直接交换两个记录，那么复制、拷贝100个字节带来的开销就会很大，因此排序的时候针对指向记录的指针进行排序，每次只需要交换两个指针，所以开销就会小很多。</p>
<p>为此，进行如下的定义</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">unsigned</span> <span class="token keyword">char</span> byte_t<span class="token punctuation">;</span>
<span class="token keyword">typedef</span> byte_t <span class="token operator">*</span>byteStream_t<span class="token punctuation">;</span>
<span class="token keyword">typedef</span> byteStream_t <span class="token operator">*</span>record_t<span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span></span></code></pre>
<p>其中：</p>
<ul>
<li>1个字节就是8个比特位，且不考虑符号，所以定义<code>byte_t</code>类型为<code>unsigned char</code></li>
<li>字节流则是由字节组成的数组，因此定义<code>byteStream_t</code>类型为指向<code>byte</code>的指针，或者说是<code>byte</code>数组，即<code>byte*</code>，所以一个记录是100字节，就可以用一个<code>byte</code>数组表示，即用<code>byteStream_t</code>表示</li>
<li>为了避免开销，所以排序是针对指向记录的指针进行的，即针对指向<code>byteStream_t</code>的指针进行的，所以定义一个<code>record_t</code>为<code>byteStream*</code></li>
</ul>
<h3 id="2-sort-job-t对象"><a href="#2-sort-job-t对象" class="headerlink" title="2. sort_job_t对象"></a>2. sort_job_t对象</h3><h4 id="A-定义"><a href="#A-定义" class="headerlink" title="A. 定义"></a>A. 定义</h4><p><code>sort_job_t</code>对象的定义如下</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> _sort_job
<span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// Notes: init 必须指定</span>
    <span class="token keyword">int</span> sort_func<span class="token punctuation">;</span>
    <span class="token keyword">int</span> seek<span class="token punctuation">;</span>
    <span class="token keyword">int</span> num<span class="token punctuation">;</span>
    bool reverse<span class="token punctuation">;</span>
    <span class="token keyword">char</span> <span class="token operator">*</span>filename<span class="token punctuation">;</span>

    <span class="token comment" spellcheck="true">// Notes: done, records和buffer由worker填充</span>
    bool done<span class="token punctuation">;</span>
    record_t <span class="token operator">*</span>records<span class="token punctuation">;</span>
    byteStream_t buffer<span class="token punctuation">;</span>
<span class="token punctuation">}</span> sort_job_t<span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>其中，在初始化<code>sort_job_t</code>类型的对象的时候，下面几个参数必须指定</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// Notes: init 必须指定</span>
<span class="token keyword">int</span> sort_func<span class="token punctuation">;</span>
<span class="token keyword">int</span> seek<span class="token punctuation">;</span>
<span class="token keyword">int</span> num<span class="token punctuation">;</span>
bool reverse<span class="token punctuation">;</span>
<span class="token keyword">char</span> <span class="token operator">*</span>filename<span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>而剩余的参数</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// Notes: done, records和buffer由worker填充</span>
bool done<span class="token punctuation">;</span>
record_t <span class="token operator">*</span>records<span class="token punctuation">;</span>
byteStream_t buffer<span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span></span></code></pre>
<p>则是由以<code>sort_job_t</code>为输入的函数所填充的，稍后会介绍。</p>
<h4 id="B-sort-job相关函数"><a href="#B-sort-job相关函数" class="headerlink" title="B. sort_job相关函数"></a>B. sort_job相关函数</h4><p><code>sort_job</code>对象作为程序的核心，不少函数都和他有关，具体来说，包括以下函数</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// sort_job 初始化、释放相关</span>
sort_job_t <span class="token operator">*</span><span class="token function">sort_job_init</span><span class="token punctuation">(</span><span class="token keyword">int</span> sort_func<span class="token punctuation">,</span> <span class="token keyword">int</span> seek<span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">,</span> <span class="token keyword">char</span> <span class="token operator">*</span>filename<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">sort_job_release</span><span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span>job<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">read_records</span><span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>filename<span class="token punctuation">,</span> byteStream_t <span class="token operator">*</span>buffer<span class="token punctuation">,</span> <span class="token keyword">int</span> seek<span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">parse_records</span><span class="token punctuation">(</span>byteStream_t buffer<span class="token punctuation">,</span> record_t <span class="token operator">*</span>records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> byte<span class="token punctuation">)</span><span class="token punctuation">;</span>

<span class="token comment" spellcheck="true">// 多线程函数，以sort_job为核心</span>
<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">sort_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">append_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">merge_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>多线程函数放在后面介绍，所以这里就先介绍<code>sort_job</code>初始化和释放的相关函数。</p>
<h4 id="C-sort-job-init与sort-job-release函数"><a href="#C-sort-job-init与sort-job-release函数" class="headerlink" title="C. sort_job_init与sort_job_release函数"></a>C. sort_job_init与sort_job_release函数</h4><p>针对<code>sort_job</code>对象，提供了下述两个个相关的函数以进行初始化和释放</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// sort_job functions</span>
sort_job <span class="token operator">*</span><span class="token function">sort_job_init</span><span class="token punctuation">(</span><span class="token keyword">int</span> sort_func<span class="token punctuation">,</span> <span class="token keyword">int</span> seek<span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">,</span> <span class="token keyword">char</span> <span class="token operator">*</span>filename<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">sort_job_release</span><span class="token punctuation">(</span>sort_job <span class="token operator">*</span>job<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span></span></code></pre>
<p>其中：</p>
<ul>
<li><code>sort_job_init</code>负责初始化<code>sort_job</code>，而由<code>sort_job_init</code>初始化的<code>sort_job</code>必须由<code>sort_job_release</code>释放</li>
<li><code>sort_job_release</code>负责释放由<code>sort_job_init</code>初始化的<code>sort_job</code></li>
</ul>
<p>两个函数具体的定义如下：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 * @brief sort_job结构体的初始化函数
 *
 * @param sort_func 使用的sort function类型
 * @param seek 跳过多少个record
 * @param num 读取的record数, -1 表示读取全部
 * @param reverse 是否降序排列，若为true则降序排序
 * @param filename 需要读取的二进制文件文件名
 * @return sort_job* 指向结构体的指针
 *
 * @author Shihong Wang
 * @date 2022.11.2
 */</span>
sort_job_t <span class="token operator">*</span><span class="token function">sort_job_init</span><span class="token punctuation">(</span><span class="token keyword">int</span> sort_func<span class="token punctuation">,</span> <span class="token keyword">int</span> seek<span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">,</span> <span class="token keyword">char</span> <span class="token operator">*</span>filename<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    sort_job_t <span class="token operator">*</span>job <span class="token operator">=</span> <span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>sort_job_t<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    job<span class="token operator">-></span>sort_func <span class="token operator">=</span> sort_func<span class="token punctuation">;</span>
    job<span class="token operator">-></span>seek <span class="token operator">=</span> seek<span class="token punctuation">;</span>
    job<span class="token operator">-></span>num <span class="token operator">=</span> num<span class="token punctuation">;</span>
    job<span class="token operator">-></span>reverse <span class="token operator">=</span> reverse<span class="token punctuation">;</span>
    job<span class="token operator">-></span>buffer <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
    job<span class="token operator">-></span>records <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token constant">NULL</span> <span class="token operator">==</span> filename<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        job<span class="token operator">-></span>filename <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">else</span>
    <span class="token punctuation">{</span>
        job<span class="token operator">-></span>filename <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token function">strlen</span><span class="token punctuation">(</span>filename<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">strcpy</span><span class="token punctuation">(</span>job<span class="token operator">-></span>filename<span class="token punctuation">,</span> filename<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> job<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token comment" spellcheck="true">/**
 * @brief sort_job的析构函数
 *
 * @param job 指向sort_job的指针
 * @return int
 *
 * @author Shihong Wang
 * @date 2022.11.3
 */</span>
<span class="token keyword">int</span> <span class="token function">sort_job_release</span><span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span>job<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token function">free</span><span class="token punctuation">(</span>job<span class="token operator">-></span>filename<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>job<span class="token operator">-></span>buffer <span class="token operator">!=</span> <span class="token constant">NULL</span><span class="token punctuation">)</span>
        <span class="token function">free</span><span class="token punctuation">(</span>job<span class="token operator">-></span>buffer<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>job<span class="token operator">-></span>records <span class="token operator">!=</span> <span class="token constant">NULL</span><span class="token punctuation">)</span>
        <span class="token function">free</span><span class="token punctuation">(</span>job<span class="token operator">-></span>records<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">free</span><span class="token punctuation">(</span>job<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="D-read-record与parse-record函数"><a href="#D-read-record与parse-record函数" class="headerlink" title="D. read_record与parse_record函数"></a>D. read_record与parse_record函数</h4><p><code>sort_job_t</code>中的<code>buffer</code>指向字节流，而<code>records</code>则是<code>record</code>数组。这两个参数由<code>read_records</code>和<code>parse_records</code>这两个函数填充</p>
<p>其中：</p>
<ul>
<li><code>read_records(const char *filename, byteStream_t *buffer, int seek, int num)</code>函数接受要读取的文件名，而后将其中的内容读取后复制到<code>buffer</code>中</li>
<li><code>parse_records(byteStream_t buffer, record_t *records[], int byte)</code>函数接受由<code>read_records</code>函数读取得到<code>buffer</code>，而后解析其中的每个record，并将指向所以<code>record</code>得指针存入<code>records</code>数组中</li>
</ul>
<p>这两个函数具体的内容如下：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 * @brief read_records_worker以以二进制方式读取filename中数据并写入到buffer中
 *
 * @param filename 二进制文件名
 * @param buffer *byteStream_t, 指向byteStream的指针，不用提前malloc分配地址
 * @param seek 跳过多少个record
 * @param num 读取的record数, -1表示从seek读取到结束, -2读取文件中全部的record
 * @return int 读取的字节数
 *
 * @author Shihong Wang
 * @date 2022.10.29
 */</span>
<span class="token keyword">int</span> <span class="token function">read_records</span><span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>filename<span class="token punctuation">,</span> byteStream_t <span class="token operator">*</span>buffer<span class="token punctuation">,</span> <span class="token keyword">int</span> seek<span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    FILE <span class="token operator">*</span>bin_file <span class="token operator">=</span> <span class="token function">fopen</span><span class="token punctuation">(</span>filename<span class="token punctuation">,</span> <span class="token string">"rb"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token constant">NULL</span> <span class="token operator">==</span> bin_file<span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"file open error"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">int</span> byte <span class="token operator">=</span> num <span class="token operator">*</span> BYTE_PER_RECORD<span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>num <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token function">fseek</span><span class="token punctuation">(</span>bin_file<span class="token punctuation">,</span> <span class="token number">0L</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        byte <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span> <span class="token function">ftell</span><span class="token punctuation">(</span>bin_file<span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token punctuation">(</span>seek <span class="token operator">*</span> BYTE_PER_RECORD<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>num <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token function">fseek</span><span class="token punctuation">(</span>bin_file<span class="token punctuation">,</span> <span class="token number">0L</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        byte <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span> <span class="token function">ftell</span><span class="token punctuation">(</span>bin_file<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>byte <span class="token operator">&lt;=</span><span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"zero record"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">fseek</span><span class="token punctuation">(</span>bin_file<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">long</span><span class="token punctuation">)</span><span class="token punctuation">(</span>seek <span class="token operator">*</span> BYTE_PER_RECORD<span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">if</span> <span class="token punctuation">(</span>byte <span class="token operator">%</span> <span class="token number">100</span> <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"record mismatch"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token operator">*</span>buffer <span class="token operator">=</span> <span class="token punctuation">(</span>byteStream_t<span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span> <span class="token operator">*</span> byte<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token constant">NULL</span> <span class="token operator">==</span> <span class="token operator">*</span>buffer<span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"malloc fail"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">fread</span><span class="token punctuation">(</span><span class="token operator">*</span>buffer<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> byte<span class="token punctuation">,</span> bin_file<span class="token punctuation">)</span> <span class="token operator">!=</span> byte<span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"record read fail"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token function">fclose</span><span class="token punctuation">(</span>bin_file<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> byte<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment" spellcheck="true">/**
 * @brief parse_records接受二进制文件buffer，将解析后的record存入records数组中
 *
 * @param buffer 二进制文件内存地址
 * @param records record数组的地址
 * @param byte 二进制文件的字节数
 * @return int 解析得到的record数
 *
 * @author Shihong Wang
 * @date 2022.10.30
 */</span>
<span class="token keyword">int</span> <span class="token function">parse_records</span><span class="token punctuation">(</span>byteStream_t buffer<span class="token punctuation">,</span> record_t <span class="token operator">*</span>records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> byte<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> num <span class="token operator">=</span> byte <span class="token operator">/</span> <span class="token number">100</span><span class="token punctuation">;</span>

    <span class="token operator">*</span>records <span class="token operator">=</span> <span class="token punctuation">(</span>record_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>record_t<span class="token punctuation">)</span> <span class="token operator">*</span> byte<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token constant">NULL</span> <span class="token operator">==</span> <span class="token operator">*</span>records<span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"malloc fail"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> num<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token punctuation">(</span><span class="token operator">*</span>records<span class="token punctuation">)</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>byteStream_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>byteStream_t<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token operator">*</span><span class="token punctuation">(</span><span class="token operator">*</span>records<span class="token punctuation">)</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>buffer <span class="token operator">+</span> <span class="token number">100</span> <span class="token operator">*</span> i<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> num<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="3-sorted-jobs队列"><a href="#3-sorted-jobs队列" class="headerlink" title="3. sorted_jobs队列"></a>3. sorted_jobs队列</h3><p>程序的多线程模型是生产者——消费者模型。核心就是生产者（<code>sort_worker</code>）、消费者（<code>merge_worker</code>）共同维护的产品队列。</p>
<p>因此，<code>sorted_jobs</code>队列作为多个线程共享的数据，对其进行修改的代码都属于临界区代码，需要使用<code>互斥锁（Mutual Exclusion, Mutex）</code>来进行保护。</p>
<p>同时，因为当<code>sorted_jobs</code>队列满了之后，生产者线程不能再继续向其中填充<code>sorted_job</code>，而当<code>sprted_job</code>空的时候，消费者线程不能继续向其中拿去<code>sorted_job</code>。所以还需要一个<code>条件变量（Conditional Variable，CV）</code>来满足生产者、消费者操作<code>sorted_jobs</code>队列的条件。</p>
<h4 id="A-定义-1"><a href="#A-定义-1" class="headerlink" title="A. 定义"></a>A. 定义</h4><p><code>sorted_jobs</code>队列相关的变量如下</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// 数组形式的循环队列</span>
<span class="token keyword">int</span> num_fill <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> front <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> rear <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
sort_job_t <span class="token operator">*</span><span class="token operator">*</span>sorted_jobs<span class="token punctuation">;</span>

<span class="token comment" spellcheck="true">// 互斥锁与信号量</span>
pthread_cond_t sorted_jobs_cond<span class="token punctuation">;</span>
pthread_mutex_t sorted_jobs_mutex<span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="B-do-get与do-fill函数"><a href="#B-do-get与do-fill函数" class="headerlink" title="B. do_get与do_fill函数"></a>B. do_get与do_fill函数</h4><p><strong><code>do_get</code>函数与<code>do_fill</code>函数是操作<code>sorted_jobs</code>的函数。</strong></p>
<p>具体来说，<code>do_get</code>负责从<code>sorted_jobs</code>队列中获取一个<code>sorted_job</code>；而<code>do_fill</code>负责向<code>sorted_jobs</code>中填充一个<code>sorted_job</code>。</p>
<p>理论上来说，可以将临界区访问的获得锁的代码放入其中，但是为了灵活性，所以选择像获得锁的代码放在<code>do_get</code>与<code>do_fill</code>函数外，即先获得锁才能调用这两个函数。</p>
<p><code>do_get</code>与<code>do_fill</code>函数的定义如下</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 * @brief do_fill用于把sorted之后的job放入sorted_jobs队列中
 *
 * @param sorted_job 指向sorted_job的指针
 *
 * @author Shihong Wang
 * @date 2022.11.3
 */</span>
<span class="token keyword">void</span> <span class="token function">do_fill</span><span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span>sorted_job<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    sorted_jobs<span class="token punctuation">[</span>rear<span class="token punctuation">]</span> <span class="token operator">=</span> sorted_job<span class="token punctuation">;</span>
    rear <span class="token operator">=</span> <span class="token punctuation">(</span>rear <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">%</span> MAX_SORTED_JOBS<span class="token punctuation">;</span>
    num_fill<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token comment" spellcheck="true">/**
 * @brief do_get用于从sorted_jobs队列中取出sorted_job
 *
 * @return sort_job* 指向sorted_job的指针
 *
 * @author Shihong Wang
 * @date 2022.11.3
 */</span>
sort_job_t <span class="token operator">*</span><span class="token function">do_get</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    sort_job_t <span class="token operator">*</span>temp <span class="token operator">=</span> sorted_jobs<span class="token punctuation">[</span>front<span class="token punctuation">]</span><span class="token punctuation">;</span>
    front <span class="token operator">=</span> <span class="token punctuation">(</span>front <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">%</span> MAX_SORTED_JOBS<span class="token punctuation">;</span>
    num_fill<span class="token operator">--</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> temp<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-if-full、if-empty与get-num函数"><a href="#C-if-full、if-empty与get-num函数" class="headerlink" title="C. if_full、if_empty与get_num函数"></a>C. if_full、if_empty与get_num函数</h4><p><code>if_full</code>、<code>if_empty</code>和<code>get_num</code>函数负责获取<code>sorted_jobs</code>队列的状态。</p>
<p>因为这三个函数只读取共享变量的值，而不会修改共享变量，因此这三个函数不是临界区代码，直接访问代码即可。</p>
<p>此外，由于在程序中汇多次调用这三个函数，因此将其声明为内联函数以加速程序运行。注意，<code>C/C++</code>要求将内联函数定义书写在头文件中。</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// libpsort.h</span>

<span class="token comment" spellcheck="true">// 函数头</span>
<span class="token keyword">static</span> <span class="token keyword">inline</span> bool <span class="token function">is_full</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">static</span> <span class="token keyword">inline</span> bool <span class="token function">is_empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">static</span> <span class="token keyword">inline</span> bool <span class="token function">get_num</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>


<span class="token comment" spellcheck="true">// Inline methods are supposed to be implemented in the header file. The compiler needs to know the code to actually inline it.</span>
<span class="token keyword">static</span> <span class="token keyword">inline</span> bool <span class="token function">is_empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">return</span> front <span class="token operator">==</span> rear<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">static</span> <span class="token keyword">inline</span> bool <span class="token function">is_full</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token punctuation">(</span>rear <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">%</span> MAX_SORTED_JOBS <span class="token operator">==</span> front<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">static</span> <span class="token keyword">inline</span> bool <span class="token function">get_num</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">return</span> num_fill<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="4-排序算法"><a href="#4-排序算法" class="headerlink" title="4. 排序算法"></a>4. 排序算法</h3><p>因为项目的架构是每个<code>sort_worker</code>负责对文件的一块内容进行排序，而后由<code>merge_worker</code>进行合并，因此程序中还需要实现排序算法。</p>
<h4 id="A-sort-func、func-name与XXX-SORT宏"><a href="#A-sort-func、func-name与XXX-SORT宏" class="headerlink" title="A. sort_func、func_name与XXX_SORT宏"></a>A. sort_func、func_name与XXX_SORT宏</h4><p>由于有多种排序算法，因此为了程序实现最高性能，需要选择尽可能快的排序算法。因此程序中实现了三种排序算法，分别是：</p>
<ul>
<li><code>冒泡排序（Bubble Sort）</code></li>
<li><code>快速排序（Quick Sort）</code></li>
<li><code>归并排序（Merge Sort)</code></li>
</ul>
<p>程序中为了方便测试三种排序算法的速度以及调试时输出信息，进行了如下规定：</p>
<blockquote>
<p>规定：排序函数的函数签名统一为：<code>sort_funct(record_t *records, int record_num, bool reverse)</code></p>
</blockquote>
<p>其中：</p>
<ul>
<li><code>record_t *records</code>是待排序的<code>record</code>数组</li>
<li><code>int record_num</code>是<code>record</code>数组中<code>record</code>的数量</li>
<li><code>bool reverse</code>表示是否降序排列，若为<code>true</code>则降序排列，否则默认升序排列</li>
</ul>
<p>因此，上述三个排序函数的函数头为</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">int</span> <span class="token function">bubble_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">quick_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">merge_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span></span></code></pre>
<p>而为了方便调试时切换函数、输出信息，定义了<code>sort_func</code>函数数组以及<code>func_name</code>字符串数组，同时为每个排序算法定义了一个宏</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token macro property">#<span class="token directive keyword">define</span> BUBBLE_SORT 0</span>
<span class="token macro property">#<span class="token directive keyword">define</span> QUICK_SORT 1</span>
<span class="token macro property">#<span class="token directive keyword">define</span> MERGE_SORT 2</span>

<span class="token keyword">char</span> <span class="token operator">*</span>func_name<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span>
    <span class="token punctuation">[</span>BUBBLE_SORT<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token string">"bubble_sort"</span><span class="token punctuation">,</span>
    <span class="token punctuation">[</span>QUICK_SORT<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token string">"quick_sort"</span><span class="token punctuation">,</span>
    <span class="token punctuation">[</span>MERGE_SORT<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token string">"merge_sort"</span><span class="token punctuation">,</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token punctuation">(</span><span class="token operator">*</span>sort_func<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">(</span>record_t <span class="token operator">*</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token punctuation">,</span> bool<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token punctuation">{</span>
    <span class="token punctuation">[</span>BUBBLE_SORT<span class="token punctuation">]</span> <span class="token operator">=</span> bubble_sort<span class="token punctuation">,</span>
    <span class="token punctuation">[</span>QUICK_SORT<span class="token punctuation">]</span> <span class="token operator">=</span> quick_sort<span class="token punctuation">,</span>
    <span class="token punctuation">[</span>MERGE_SORT<span class="token punctuation">]</span> <span class="token operator">=</span> merge_sort<span class="token punctuation">,</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>这样，在调试的时候只需要通过下述方式，即可便捷的切换排序算法以及输出调试信息</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// 调试</span>
<span class="token keyword">int</span> func <span class="token operator">=</span> BUBBLE_SORT<span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// 选择使用冒泡排序</span>
<span class="token comment" spellcheck="true">// int func = MERGE_SORT; // 选择使用归并排序</span>
<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"function used: %d, sort algorithm: %s\n"</span><span class="token punctuation">,</span> func<span class="token punctuation">,</span> func_name<span class="token punctuation">[</span>func<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
sort_func<span class="token punctuation">[</span>func<span class="token punctuation">]</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> num<span class="token punctuation">,</span> false<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="B-get-key、less-than和swap函数"><a href="#B-get-key、less-than和swap函数" class="headerlink" title="B. get_key、less_than和swap函数"></a>B. get_key、less_than和swap函数</h4><p>无论任何的函数，在排序的过程中都涉及到<code>比大小（Compare）</code>和<code>交换（Swap）</code>两个操作。因此可以将这两个常用函数单独实现。</p>
<p>此外，由于我们再比大小的时候是针对每一个<code>record</code>的<code>key</code>进行的比较，还需要一个<code>get_key</code>函数，接受<code>record</code>返回其<code>key</code>值。</p>
<p>由于这三个函数都非常常用，因此统一声明为内联函数。</p>
<p>注意，<code>C</code>语言中的<code>static</code>关键字用于声明某个变量的链接属性，因此在这里声明了<code>static</code>之后，链接的时候所有的<code>get_key</code>变量名都会链接到这里定义的<code>get_key</code>函数中。</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// libpsort.h</span>

<span class="token comment" spellcheck="true">/**
 * @brief get_key 从给定的record中读取key（前四个字节拼接得到的signed int）
 *
 * @param record 需要读取key的record
 * @return int record的key
 *
 * @author Shihong Wang
 * @date 2022.10.30
 */</span>
<span class="token keyword">static</span> <span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">get_key</span><span class="token punctuation">(</span>record_t record<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token constant">NULL</span> <span class="token operator">==</span> record<span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"record == NULL, didn't initialize?"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token operator">*</span><span class="token punctuation">(</span><span class="token keyword">int</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token punctuation">(</span><span class="token operator">*</span>record<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token comment" spellcheck="true">/**
 * @brief less_than比较两个record的key，若左边小于右边，返回1，相等返回0，大于返回-1
 *
 * @param left 左侧的Record
 * @param right 右侧的Record
 * @return int 比较的结果
 *
 * @author Shihong Wang
 * @date 2022.10.30
 */</span>
<span class="token keyword">static</span> <span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">less_than</span><span class="token punctuation">(</span>record_t left<span class="token punctuation">,</span> record_t right<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> left_key <span class="token operator">=</span> <span class="token function">get_key</span><span class="token punctuation">(</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> right_key <span class="token operator">=</span> <span class="token function">get_key</span><span class="token punctuation">(</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>left_key <span class="token operator">&lt;</span> right_key<span class="token punctuation">)</span>
        <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>left_key <span class="token operator">==</span> right_key<span class="token punctuation">)</span>
        <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">else</span>
        <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token comment" spellcheck="true">/**
 * @brief swap用于交换record数组中指令的两个元素
 *
 * @param records record数组
 * @param i 第一个元素的index
 * @param j 第二个元素的index
 *
 * @author Shihong Wang
 * @date 2022.10.30
 */</span>
<span class="token keyword">static</span> <span class="token keyword">inline</span> <span class="token keyword">void</span> <span class="token function">swap</span><span class="token punctuation">(</span>record_t <span class="token operator">*</span>records<span class="token punctuation">,</span> <span class="token keyword">int</span> i<span class="token punctuation">,</span> <span class="token keyword">int</span> j<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    record_t temp <span class="token operator">=</span> records<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
    records<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> records<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
    records<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-冒泡排序算法实现"><a href="#C-冒泡排序算法实现" class="headerlink" title="C. 冒泡排序算法实现"></a>C. 冒泡排序算法实现</h4><p>冒泡排序算法实现如下，没啥好说的，写就对了。</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 * @brief 冒泡排序，大保底
 *
 * @param records record数组
 * @param num record的数量
 * @param reverse 若为true，则按照降序排列，否则按照升序排列
 * @return int 状态码
 *
 * @author Shihong Wang
 * @date 2022.10.30
 */</span>
<span class="token keyword">int</span> <span class="token function">bubble_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> sign <span class="token operator">=</span> reverse <span class="token operator">==</span> true <span class="token operator">?</span> <span class="token number">1</span> <span class="token punctuation">:</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> num<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> num <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">-</span> i<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">less_than</span><span class="token punctuation">(</span>records<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> records<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">*</span> sign <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">)</span>
                <span class="token function">swap</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> j<span class="token punctuation">,</span> j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> SORT_SUCCESS<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="D-快速排序算法实现"><a href="#D-快速排序算法实现" class="headerlink" title="D. 快速排序算法实现"></a>D. 快速排序算法实现</h4><p>快速排序有好几种实现方式，最简单的就是递归实现。递归实现的首先根据当前枢轴的值，将数组中小于枢轴值的<code>record</code>放到左侧，大于枢轴值的<code>record</code>放到右侧。而后分别对左侧和右侧进行递归排序</p>
<p>因此对其递归函数进行封装，提供统一的排序函数调用接口：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// 函数头</span>
<span class="token keyword">int</span> <span class="token function">_partition</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">_quick_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">quick_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span></span></code></pre>
<p>函数具体实现为：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 * @brief 快速排序的partition函数
 *
 * @param records record数组
 * @param low 左侧index
 * @param high 右侧index
 * @param reverse 若为true，则按照降序排列，否则按照生序排列
 * @return int 新的pivot的index
 *
 * @author Shihong Wang
 * @date 2022.10.31
 */</span>
<span class="token keyword">int</span> <span class="token function">_partition</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> pivot <span class="token operator">=</span> low<span class="token punctuation">;</span>
    record_t pivot_value <span class="token operator">=</span> records<span class="token punctuation">[</span>pivot<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> sign <span class="token operator">=</span> reverse <span class="token operator">==</span> true <span class="token operator">?</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">:</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>low <span class="token operator">&lt;</span> high<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>low <span class="token operator">&lt;</span> high <span class="token operator">&amp;&amp;</span> <span class="token function">less_than</span><span class="token punctuation">(</span>pivot_value<span class="token punctuation">,</span> records<span class="token punctuation">[</span>high<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">*</span> sign <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">)</span>
            high<span class="token operator">--</span><span class="token punctuation">;</span>
        records<span class="token punctuation">[</span>low<span class="token punctuation">]</span> <span class="token operator">=</span> records<span class="token punctuation">[</span>high<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>low <span class="token operator">&lt;</span> high <span class="token operator">&amp;&amp;</span> <span class="token function">less_than</span><span class="token punctuation">(</span>records<span class="token punctuation">[</span>low<span class="token punctuation">]</span><span class="token punctuation">,</span> pivot_value<span class="token punctuation">)</span> <span class="token operator">*</span> sign <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">)</span>
            low<span class="token operator">++</span><span class="token punctuation">;</span>
        records<span class="token punctuation">[</span>high<span class="token punctuation">]</span> <span class="token operator">=</span> records<span class="token punctuation">[</span>low<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    records<span class="token punctuation">[</span>low<span class="token punctuation">]</span> <span class="token operator">=</span> pivot_value<span class="token punctuation">;</span>
    <span class="token keyword">return</span> low<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token comment" spellcheck="true">/**
 * @brief 快速排序母函数
 *
 * @param records record数组
 * @param low 左侧index
 * @param high 右侧index
 * @param reverse 若为true则降序排列，否则升序排列
 * @return int 程序状态码
 *
 * @author Shihong Wang
 * @date 2022.10.31
 */</span>
<span class="token keyword">int</span> <span class="token function">_quick_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>low <span class="token operator">&lt;</span> high<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">int</span> pivot <span class="token operator">=</span> <span class="token function">_partition</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> low<span class="token punctuation">,</span> high<span class="token punctuation">,</span> reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">_quick_sort</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> low<span class="token punctuation">,</span> pivot <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">_quick_sort</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> pivot <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> high<span class="token punctuation">,</span> reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> SORT_SUCCESS<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token comment" spellcheck="true">/**
 * @brief 快速排序 wrapper，为了benchmark
 *
 * @param records record数组
 * @param num record的数量
 * @param reverse 若为true，则按照降序排列，否则按照升序排列
 * @return int 状态码
 *
 * @author Shihong Wang
 * @date 2022.10.31
 */</span>
<span class="token keyword">int</span> <span class="token function">quick_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token function">_quick_sort</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> num <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="E-归并排序算法实现"><a href="#E-归并排序算法实现" class="headerlink" title="E. 归并排序算法实现"></a>E. 归并排序算法实现</h4><p>归并排序中的归并这一步由于在<code>merge_worker</code>中也有所使用，因此将其单独封装为一个函数。</p>
<p>归并排序的函数头为：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">int</span> <span class="token function">order_merge</span><span class="token punctuation">(</span>record_t old_records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> record_t new_records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> <span class="token keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> mid<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">_merge_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">,</span> <span class="token keyword">int</span> seg_start<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">merge_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span></span></code></pre>
<p>其中<code>order_merge</code>为将<code>old_records</code>中<code>low</code>~<code>mid</code>已经排序好的<code>record</code>和<code>mid+1</code>~<code>high</code>中已经排序好的<code>record</code>进行合并</p>
<p>三个函数的实现分别如下</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 * @brief order_merge 给定未排序的原数组和空的新数组，而后将low ~ mid 和 mid ~ high中的值按顺序排列到新数组中
 *
 * @param old_records 原数组
 * @param new_records 新数组
 * @param num 原数组中record数
 * @param low low的值
 * @param mid mid的值
 * @param high high的值
 * @param reverse 若为true，则为降序排列，否则为升序排列
 * @return int 状态码
 *
 * @author Shihong Wang
 * @date 2022.11.3
 */</span>
<span class="token keyword">int</span> <span class="token function">order_merge</span><span class="token punctuation">(</span>record_t old_records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> record_t new_records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> <span class="token keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> mid<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> k <span class="token operator">=</span> low<span class="token punctuation">;</span>
    <span class="token keyword">int</span> start1 <span class="token operator">=</span> low<span class="token punctuation">,</span> end1 <span class="token operator">=</span> mid<span class="token punctuation">;</span>
    <span class="token keyword">int</span> start2 <span class="token operator">=</span> mid<span class="token punctuation">,</span> end2 <span class="token operator">=</span> high<span class="token punctuation">;</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>start1 <span class="token operator">&lt;</span> end1 <span class="token operator">&amp;&amp;</span> start2 <span class="token operator">&lt;</span> end2<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>reverse<span class="token punctuation">)</span>
            new_records<span class="token punctuation">[</span>k<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">less_than</span><span class="token punctuation">(</span>old_records<span class="token punctuation">[</span>start1<span class="token punctuation">]</span><span class="token punctuation">,</span> old_records<span class="token punctuation">[</span>start2<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">>=</span> <span class="token number">0</span> <span class="token operator">?</span> old_records<span class="token punctuation">[</span>start1<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token punctuation">:</span> old_records<span class="token punctuation">[</span>start2<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span>
            new_records<span class="token punctuation">[</span>k<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">less_than</span><span class="token punctuation">(</span>old_records<span class="token punctuation">[</span>start1<span class="token punctuation">]</span><span class="token punctuation">,</span> old_records<span class="token punctuation">[</span>start2<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">>=</span> <span class="token number">0</span> <span class="token operator">?</span> old_records<span class="token punctuation">[</span>start2<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token punctuation">:</span> old_records<span class="token punctuation">[</span>start1<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>start1 <span class="token operator">&lt;</span> end1<span class="token punctuation">)</span>
        new_records<span class="token punctuation">[</span>k<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> old_records<span class="token punctuation">[</span>start1<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>start2 <span class="token operator">&lt;</span> end2<span class="token punctuation">)</span>
        new_records<span class="token punctuation">[</span>k<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> old_records<span class="token punctuation">[</span>start2<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token comment" spellcheck="true">/**
 * @brief 归并排序母函数
 *
 * @param records record数组
 * @param num record的数量
 * @param reverse 若为true，则按照降序排列，否则按照升序排列
 * @param seg_start 归并排序开始时每组中的记录数
 * @return int 状态码
 *
 * @author Shihong Wang
 * @date 2022.11.3
 */</span>
<span class="token keyword">int</span> <span class="token function">_merge_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">,</span> <span class="token keyword">int</span> seg_start<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> sign <span class="token operator">=</span> reverse <span class="token operator">==</span> true <span class="token operator">?</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">:</span> <span class="token number">1</span><span class="token punctuation">;</span>
    record_t <span class="token operator">*</span>old_records <span class="token operator">=</span> records<span class="token punctuation">;</span>
    record_t <span class="token operator">*</span>new_records <span class="token operator">=</span> <span class="token punctuation">(</span>record_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>record_t<span class="token punctuation">)</span> <span class="token operator">*</span> num<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> seg<span class="token punctuation">,</span> start<span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span>seg <span class="token operator">=</span> seg_start<span class="token punctuation">;</span> seg <span class="token operator">&lt;</span> num<span class="token punctuation">;</span> seg <span class="token operator">+</span><span class="token operator">=</span> seg<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span>start <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> start <span class="token operator">&lt;</span> num<span class="token punctuation">;</span> start <span class="token operator">+</span><span class="token operator">=</span> seg <span class="token operator">*</span> <span class="token number">2</span><span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">int</span> low <span class="token operator">=</span> start<span class="token punctuation">,</span> mid <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>start <span class="token operator">+</span> seg<span class="token punctuation">,</span> num<span class="token punctuation">)</span><span class="token punctuation">,</span> high <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>start <span class="token operator">+</span> seg <span class="token operator">*</span> <span class="token number">2</span><span class="token punctuation">,</span> num<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token function">order_merge</span><span class="token punctuation">(</span>old_records<span class="token punctuation">,</span> new_records<span class="token punctuation">,</span> num<span class="token punctuation">,</span> low<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> high<span class="token punctuation">,</span> reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment" spellcheck="true">// swap for next sort</span>
        record_t <span class="token operator">*</span>temp <span class="token operator">=</span> new_records<span class="token punctuation">;</span>
        new_records <span class="token operator">=</span> old_records<span class="token punctuation">;</span>
        old_records <span class="token operator">=</span> temp<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">if</span> <span class="token punctuation">(</span>old_records <span class="token operator">!=</span> records<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> num<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
            new_records<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> old_records<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        new_records <span class="token operator">=</span> old_records<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token function">free</span><span class="token punctuation">(</span>new_records<span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> SORT_SUCCESS<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token comment" spellcheck="true">/**
 * @brief 归并排序 wrapper, 为了benchmark
 *
 * @param records
 * @param num
 * @param reverse
 * @return int
 *
 * @author Shihong Wang
 * @date 2022.11.3
 */</span>
<span class="token keyword">int</span> <span class="token function">merge_sort</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">,</span> bool reverse<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token function">_merge_sort</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> num<span class="token punctuation">,</span> reverse<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="5-多线程排序"><a href="#5-多线程排序" class="headerlink" title="5. 多线程排序"></a>5. 多线程排序</h3><p>多线程排序的核心算法就是两类线程：<code>生产者</code>和<code>消费者</code>。其中<code>sort_worker</code>由于对<code>sort_job</code>排序后将其放入<code>sorted_jobs</code>队列中，因此<code>sort_worker</code>是生产者，而<code>merge_worker</code>由于从<code>sorted_jobs</code>中获取<code>sorted_job</code>，因此是消费者。</p>
<h4 id="A-生产者：sort-worker"><a href="#A-生产者：sort-worker" class="headerlink" title="A. 生产者：sort_worker"></a>A. 生产者：sort_worker</h4><p>生产者<code>sort_worker</code>的函数头如下：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">sort_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span></span></code></pre>
<p>由于<code>pthread</code>库要求传入的参数是一个指针，因此在调用的时候需要将原始的参数转换为指向<code>void</code>的指针，而后在函数中再将其转换为原先的指针。即：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// 按照如下方式创建线程</span>
<span class="token keyword">int</span> func <span class="token operator">=</span> MERGE_SORT<span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// 使用归并排序</span>
<span class="token keyword">int</span> seek <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// 从头开始读取文件</span>
<span class="token keyword">int</span> num <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// 读取文件中全部record</span>
bool reverse <span class="token operator">=</span> false<span class="token punctuation">;</span>
<span class="token keyword">char</span> <span class="token operator">*</span>filename <span class="token operator">=</span> <span class="token string">"test.bin"</span><span class="token punctuation">;</span>
<span class="token comment" spellcheck="true">// 初始化sort_job</span>
job <span class="token operator">=</span> <span class="token function">sort_job_init</span><span class="token punctuation">(</span>MERGE_SORT<span class="token punctuation">,</span> seek<span class="token punctuation">,</span> num<span class="token punctuation">,</span> reverse<span class="token punctuation">,</span> filename<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sort_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> sort_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span>jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>


<span class="token comment" spellcheck="true">// sort_worker按照如下方式接受参数</span>
<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">sort_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
      <span class="token comment" spellcheck="true">// sort_worker认领sort_job，而后开始排序</span>
    sort_job_t <span class="token operator">*</span>job <span class="token operator">=</span> <span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span><span class="token punctuation">)</span>arg<span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 开始排序</span>
         <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> 
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><code>sort_worker</code>整体实现为：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 * @brief sort_worker是排序线程执行的函数，每个sort_worker都是一个producer(产品放在sorted_queue中)
 *
 * @param arg 指向sort_job*的指针，传入前和使用前都需要进行类型强制转换
 * @return void*
 *
 * @author Shihong Wang
 * @date 2022.11.3
 */</span>
<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">sort_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
      <span class="token comment" spellcheck="true">// 领取sort_job（接受参数）</span>
    sort_job_t <span class="token operator">*</span>job <span class="token operator">=</span> <span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span><span class="token punctuation">)</span>arg<span class="token punctuation">;</span>

      <span class="token comment" spellcheck="true">// 读取record</span>
    <span class="token keyword">int</span> byte <span class="token operator">=</span> <span class="token function">read_records</span><span class="token punctuation">(</span>job<span class="token operator">-></span>filename<span class="token punctuation">,</span> <span class="token operator">&amp;</span>job<span class="token operator">-></span>buffer<span class="token punctuation">,</span> job<span class="token operator">-></span>seek<span class="token punctuation">,</span> job<span class="token operator">-></span>num<span class="token punctuation">)</span><span class="token punctuation">;</span>
    job<span class="token operator">-></span>num <span class="token operator">=</span> byte <span class="token operator">/</span> <span class="token number">100</span><span class="token punctuation">;</span>

    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">parse_records</span><span class="token punctuation">(</span>job<span class="token operator">-></span>buffer<span class="token punctuation">,</span> <span class="token operator">&amp;</span>job<span class="token operator">-></span>records<span class="token punctuation">,</span> byte<span class="token punctuation">)</span> <span class="token operator">!=</span> job<span class="token operator">-></span>num<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">char</span> str<span class="token punctuation">[</span>MAX_CHAR<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token function">sprintf</span><span class="token punctuation">(</span>str<span class="token punctuation">,</span> <span class="token string">"thd -> %ld: parse_records mismatch!"</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">long</span><span class="token punctuation">)</span><span class="token function">pthread_self</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span>str<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

      <span class="token comment" spellcheck="true">// 排序</span>
    <span class="token keyword">int</span> result <span class="token operator">=</span> sort_func<span class="token punctuation">[</span>job<span class="token operator">-></span>sort_func<span class="token punctuation">]</span><span class="token punctuation">(</span>job<span class="token operator">-></span>records<span class="token punctuation">,</span> job<span class="token operator">-></span>num<span class="token punctuation">,</span> job<span class="token operator">-></span>reverse<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>result <span class="token operator">!=</span> SORT_SUCCESS<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">char</span> str<span class="token punctuation">[</span>MAX_CHAR<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token function">sprintf</span><span class="token punctuation">(</span>str<span class="token punctuation">,</span> <span class="token string">"thd -> %ld: sort fail!"</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">long</span><span class="token punctuation">)</span><span class="token function">pthread_self</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span>str<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    job<span class="token operator">-></span>done <span class="token operator">=</span> true<span class="token punctuation">;</span>


      <span class="token comment" spellcheck="true">// 将排序完的任务（sorted_job）放入sorted_jobs队列中</span>

    <span class="token comment" spellcheck="true">// 下面因为要访问共享资源sorted_jobs，所以都是临界区</span>
    <span class="token function">pthread_mutex_lock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 等待consumer</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">is_full</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token function">pthread_cond_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">,</span> <span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 排序完当前job后，把job放入sorted_jobs_queue中，等待merger_worker处理，所以sort_worker就是producer</span>
    <span class="token function">do_fill</span><span class="token punctuation">(</span>job<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 唤醒consumer</span>
    <span class="token function">pthread_cond_signal</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_mutex_unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="B-生产者：append-worker"><a href="#B-生产者：append-worker" class="headerlink" title="B. 生产者：append_worker"></a>B. 生产者：append_worker</h4><p><code>merge_worker</code>在合并开始前从<code>sorted_jobs</code>中获取两个<code>sorted_job</code>，因此<code>merge_worker</code>是消费者。而当<code>merge_worker</code>在归并完成后，需要将新的、合并后<code>record</code>数量更多的<code>sorted_job</code>插入到<code>sorted_jobs</code>队列中，因此<code>merge_worker</code>也是消费者。</p>
<p>换而言之，<code>merge_worker</code>既是消费者，也是生产者。可是由于<code>sort_worker</code>是生产者，因此下述情况下可能会发生死锁：</p>
<ul>
<li>条件一：<code>sorted_jobs</code>队列已满</li>
<li>条件二：<code>merge_worker</code>开始运行</li>
<li>条件三：<code>merge_worker</code>在从<code>sorted_jobs</code>中取出两个<code>sorted_job</code>后，由于线程调度被中断运行。</li>
<li>条件四：此时其他<code>sorted_worker</code>完成排序，将<code>sorted_jobs</code>填充满</li>
<li>条件五：继续运行<code>merge_worker</code></li>
</ul>
<p>由于在获得两个<code>sorted_jobs</code>后，<code>merge_worker</code>就从消费者变成了生产者。则此时<code>sorted_jobs</code>已经完全填充满，并且系统中不存在其他消费者，只有生产者，则此时发生死锁，系统卡死。</p>
<p>导致该问题发生的关键就是<code>merge_worker</code>既是消费者，也是生产者。因此解决方案就是将<code>merge_worker</code>修改为纯粹的消费者，而向<code>sorted_jobs</code>中插入新的<code>sorted_job</code>的工作则交给新的线程<code>append_worker</code>即可。这样<code>merge_worker</code>就可以继续进行合并。</p>
<p>即：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">append_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span><span class="token punctuation">{</span>
    sort_job_t <span class="token operator">*</span>job <span class="token operator">=</span> <span class="token punctuation">(</span>sort_job_t<span class="token operator">*</span><span class="token punctuation">)</span> arg<span class="token punctuation">;</span>
      <span class="token comment" spellcheck="true">// 插入操作</span>
      <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
    <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token keyword">void</span><span class="token operator">*</span><span class="token punctuation">)</span><span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>



<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">merge_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span>
<span class="token punctuation">{</span>   
  <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
     <span class="token keyword">while</span> <span class="token punctuation">(</span>true <span class="token operator">&amp;&amp;</span> <span class="token operator">!</span>last_job<span class="token punctuation">)</span>
  <span class="token punctuation">{</span>
        <span class="token function">get_two_jobs</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">merge_to_job</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>

        <span class="token comment" spellcheck="true">// 将新的job插入到循环队列尾</span>
      pthread_t append_thd<span class="token punctuation">;</span>
      <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>append_thd<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> append_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span>job<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>如此，即可避免该死锁问题。</p>
<p><code>append_worker</code>具体实现为</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 * @brief append_worker是append线程执行的函数，每个append_worker都是producer
 * 
 * @param arg (sort_job*)指向sort_job的结构体
 * @return void* 程序状态码
 * 
 * @author Shihong Wang
 * @date 2022.11.3
 */</span>
<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">append_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span><span class="token punctuation">{</span>
    sort_job_t <span class="token operator">*</span>job <span class="token operator">=</span> <span class="token punctuation">(</span>sort_job_t<span class="token operator">*</span><span class="token punctuation">)</span> arg<span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 下面因为要访问共享资源sorted_jobs，所以都是临界区</span>
    <span class="token function">pthread_mutex_lock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// Attention: 如果sorted_jobs已满(其他sort_worker/merge_worker线程填充)，且只有一个consumer，则此时会有卡住，所以要保证sorted_job有足够的容量，即sorted_job &lt; sort_thread + merge_thread</span>
    <span class="token comment" spellcheck="true">// 等待consumer</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">is_full</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token function">pthread_cond_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">,</span> <span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 排序完当前job后，把job放入sorted_jobs_queue中，等待merger_worker处理，所以sort_worker就是producer</span>
    <span class="token function">do_fill</span><span class="token punctuation">(</span>job<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 唤醒consumer</span>
    <span class="token function">pthread_cond_signal</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_mutex_unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token keyword">void</span><span class="token operator">*</span><span class="token punctuation">)</span><span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-消费者：merge-worker"><a href="#C-消费者：merge-worker" class="headerlink" title="C. 消费者：merge_worker"></a>C. 消费者：merge_worker</h4><p><code>merge_worker</code>的基本结构为：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">merge_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span>
<span class="token punctuation">{</span>   
    bool last_job <span class="token operator">=</span> false<span class="token punctuation">;</span>
      <span class="token comment" spellcheck="true">// 不是最后一个merge_job，继续合并</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>not last_job<span class="token punctuation">)</span><span class="token punctuation">{</span>
          <span class="token comment" spellcheck="true">// 获取两个sorted_job</span>
          sorted_job1 <span class="token operator">=</span> <span class="token function">get_sorted_job</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
          sorted_job2 <span class="token operator">=</span> <span class="token function">get_sorted_job</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

          <span class="token comment" spellcheck="true">// 合并两个sorted_job</span>
          new_sorted_job <span class="token operator">=</span> <span class="token function">merge_two_job</span><span class="token punctuation">(</span>sorted_job1<span class="token punctuation">,</span> sorted_job2<span class="token punctuation">)</span><span class="token punctuation">;</span>

          <span class="token comment" spellcheck="true">// 插入新的sorted_job</span>
          <span class="token function">append_sorted_job</span><span class="token punctuation">(</span>new_sorted_job<span class="token punctuation">)</span><span class="token punctuation">;</span>

          <span class="token comment" spellcheck="true">// 检查是否为最后一个job</span>
          last_job <span class="token operator">=</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
  <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token keyword">void</span><span class="token operator">*</span><span class="token punctuation">)</span><span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>但是此架构在下述情况下存在死锁：</p>
<ul>
<li>条件一：所有<code>sort_worker</code>已经完成排序，即无新的<code>sorted_job</code>产生</li>
<li>条件二：只有两个<code>sorted_job</code>等待合并</li>
<li>条件三：有两个<code>merge_worker</code>，每个<code>merge_worker</code>都只有一个<code>sorted_job</code></li>
</ul>
<p>此时，系统中已经没有新的生产者，只有消费者，并且两个消费者互相等待对方手中的资源，即<code>merge_worker</code>互相等待对方的<code>sorted_job</code></p>
<p>则此时系统发生死锁。</p>
<p>该死锁最简单的处理方式就是要求消费者主动归还资源，即在等待一段时间得不到新的<code>sorted_job</code>后，默认存在另外一个<code>merge_worker</code>，则此时放弃已经拿到的<code>sorted_job</code>，并且结束此<code>merge_worker</code>。</p>
<p>形象的理解，孔融需要吃到两个梨子，如果只有一个梨子，并且等待了一段时间后得不到新的梨子，就让出梨子，让别人来吃梨子。</p>
<p>则此时，<code>merge_worker</code>的结构如下</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">merge_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span>
<span class="token punctuation">{</span>   
    bool last_job <span class="token operator">=</span> false<span class="token punctuation">;</span>
      <span class="token comment" spellcheck="true">// 不是最后一个merge_job，继续合并</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>not last_job<span class="token punctuation">)</span><span class="token punctuation">{</span>
          <span class="token comment" spellcheck="true">// 获取两个sorted_job</span>
          sort_job jobs<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token constant">NULL</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">}</span><span class="token punctuation">;</span>
          <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">2</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
              <span class="token comment" spellcheck="true">// 等待500毫秒，若成功返回1，否则返回0</span>
              bool success <span class="token operator">=</span> <span class="token function">get_sorted_job_timeout</span><span class="token punctuation">(</span>job<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>  <span class="token number">500</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
              <span class="token keyword">if</span> <span class="token punctuation">(</span>not success<span class="token punctuation">)</span><span class="token punctuation">{</span>
                  <span class="token function">giveup</span><span class="token punctuation">(</span>jobs<span class="token punctuation">)</span><span class="token punctuation">;</span>
                  <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token keyword">void</span><span class="token operator">*</span><span class="token punctuation">)</span> <span class="token number">0</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>


          <span class="token comment" spellcheck="true">// 合并两个sorted_job</span>
          new_sorted_job <span class="token operator">=</span> <span class="token function">merge_two_job</span><span class="token punctuation">(</span>jobs<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">,</span> jobs<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

          <span class="token comment" spellcheck="true">// 插入新的sorted_job</span>
          <span class="token function">append_sorted_job</span><span class="token punctuation">(</span>new_sorted_job<span class="token punctuation">)</span><span class="token punctuation">;</span>

          <span class="token comment" spellcheck="true">// 检查是否为最后一个job</span>
          last_job <span class="token operator">=</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
  <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token keyword">void</span><span class="token operator">*</span><span class="token punctuation">)</span><span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>然而，<code>孔融让梨</code>接法在大多数情况下可以正确运行，然后在部分时候将会导致新的问题：<strong>两个孔融互相让梨</strong>，即两个线程同时发现拿不到新的<code>sort_job</code>，于是都主动选择让出<code>sorted_job</code>并结束自己的声明，则此时在<code>sorted_jobs</code>队列中遗留两个未合并的<code>sorted_job</code>。</p>
<p><strong>为了解决该问题，可以指定一个不会让梨的孔融，其余的孔融全部为让梨的孔融，这样就会保证永远会存在一个孔融来吃完最后的两个梨子。</strong></p>
<p>因此，在启动<code>merge_worker</code>线程的时候，可以按照如下的方式进行启动：</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// main函数</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
      <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
      <span class="token comment" spellcheck="true">// 启动merge线程</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>merge_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
            <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>merge_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> merge_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>不让梨<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span>
            <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>merge_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> merge_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>让梨<span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>因此，<code>merge_worker</code>最终的实现为</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 * @brief merge_worker是merge线程执行的函数，每个merge_worker是消费者
 *
 * @param arg 指向int的指针，用于判断是否已经排序完毕，调用前和使用前必须要进行强制类型转换
 * @return void*
 *
 * @bug #1 多个sort_worker，一个merge_worker，下述情况会发生死锁:
 *          merge_worker正在merge，而sorted_jobs已经全部运行完，并且填充满sorted_jobs，
 *          则此时由于sorted_jobs已经被填充满，故此时merge_worker等待consumer消耗sorted_jobs
 *          由于只有一个merge_worker，故此时就会卡在这里
 *      该bug修复方式是满足：sort_worker_thd + merge_worker_thd &lt; max_sorted_jobs
 * 
 * @bug #2 多个sort_worker，一个merge_worker，下述情况会发生死锁:
 *          merge_worker在取完了sorted_job后，就从消费者变成了生产者，若此时有别的sort_worker填满了sorted_jobs
 *          后仍有sort_worker尝试do_fill，就会造成只有生产者而没有消费者的情况，此时merge_worker和sort_worker都会因为cv卡住
 *      该bug的修复方式就是将merge_worker拆分为sort_worker，重新插入的工作交给append_worker处理（子线程），以保证merge_worker不会等待
 * 
 * @bug #3 多个sort_worker，多个merge_worker，会发生死锁:
 *          已经没有了sort_worker，而所有的merge_worker都只有一个job，则此时发生死锁
 *          此bug类似于哲学家进餐问题，可以使用一个服务生（管理员）来管理、启动merge_worker
 *      该bug的修复方法就是等待一段时间后放弃merge，将job放回队列中，同时必须要有一个不会timeout的merge_thread
 *
 * @author Shihong Wang
 * @date 2022.11.4
 */</span>
<span class="token keyword">void</span> <span class="token operator">*</span><span class="token function">merge_worker</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>arg<span class="token punctuation">)</span>
<span class="token punctuation">{</span>   
    <span class="token comment" spellcheck="true">// 是否让梨？</span>
    bool wait <span class="token operator">=</span> <span class="token operator">*</span><span class="token punctuation">(</span>bool <span class="token operator">*</span><span class="token punctuation">)</span>arg<span class="token punctuation">;</span>

      <span class="token comment" spellcheck="true">// 变量声明</span>
    bool last_job <span class="token operator">=</span> false<span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// Notes: 不知道为什么，先malloc在free就不会报错，真的不理解为什么，难道是Copy-on-Write机制？真搞不明白</span>
    sort_job_t <span class="token operator">*</span>job <span class="token operator">=</span> <span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>sort_job_t<span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">free</span><span class="token punctuation">(</span>job<span class="token punctuation">)</span><span class="token punctuation">;</span>
    job <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>

    <span class="token comment" spellcheck="true">// 合并主循环，循环每运行一次，就合并两个sorted_job并插入新的sorter_job到sorted_jobs队列中</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>true <span class="token operator">&amp;&amp;</span> <span class="token operator">!</span>last_job<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>   
        <span class="token comment" spellcheck="true">// 变量声明</span>
        last_job <span class="token operator">=</span> false<span class="token punctuation">;</span>
        bool giveup <span class="token operator">=</span> false<span class="token punctuation">,</span> merge <span class="token operator">=</span> true<span class="token punctuation">;</span>
        <span class="token keyword">int</span> fill_ptr <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        sort_job_t <span class="token operator">*</span>jobs<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token constant">NULL</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">}</span><span class="token punctuation">;</span>

          <span class="token comment" spellcheck="true">// 先获取两个梨子</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>fill_ptr <span class="token operator">&lt;</span> <span class="token number">2</span> <span class="token operator">&amp;&amp;</span> <span class="token operator">!</span>last_job <span class="token operator">&amp;&amp;</span> <span class="token operator">!</span>giveup<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>   
            <span class="token keyword">int</span> state<span class="token punctuation">;</span>
            <span class="token keyword">struct</span> timeval now<span class="token punctuation">;</span>
            <span class="token keyword">struct</span> timespec expire<span class="token punctuation">;</span>
            <span class="token function">gettimeofday</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>now<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment" spellcheck="true">// Attention: 等待一会，否则放弃</span>
            expire<span class="token punctuation">.</span>tv_sec <span class="token operator">=</span> now<span class="token punctuation">.</span>tv_sec<span class="token punctuation">;</span>
            expire<span class="token punctuation">.</span>tv_nsec <span class="token operator">=</span> now<span class="token punctuation">.</span>tv_usec <span class="token operator">+</span> <span class="token number">500000000</span><span class="token punctuation">;</span>

            <span class="token comment" spellcheck="true">// 下面因为要访问共享资源sorted_jobs，所以都是临界区</span>
            <span class="token function">pthread_mutex_lock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment" spellcheck="true">// 等待看看有没有新的梨子</span>
            <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">is_empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>wait<span class="token punctuation">)</span>
                    state <span class="token operator">=</span> <span class="token function">pthread_cond_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">,</span> <span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">else</span>
                    state <span class="token operator">=</span> <span class="token function">pthread_cond_timedwait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">,</span> <span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">,</span> <span class="token operator">&amp;</span>expire<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token comment" spellcheck="true">// 等待不到新的梨子，则返还已经拿到的梨子，并且结束线程</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>state <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                    giveup <span class="token operator">=</span> true<span class="token punctuation">;</span>
                    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">2</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                        <span class="token keyword">if</span> <span class="token punctuation">(</span>jobs<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                            <span class="token function">do_fill</span><span class="token punctuation">(</span>jobs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                            jobs<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
                        <span class="token punctuation">}</span>
                    <span class="token punctuation">}</span>
                    fill_ptr <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
                    <span class="token keyword">break</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
            <span class="token comment" spellcheck="true">// 如果有新的梨子，则拿走新的梨子</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>state <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                jobs<span class="token punctuation">[</span>fill_ptr<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">do_get</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token comment" spellcheck="true">// 唤醒consumer</span>
            <span class="token function">pthread_cond_signal</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">)</span><span class="token punctuation">;</span>
              <span class="token comment" spellcheck="true">// 退出临界区</span>
            <span class="token function">pthread_mutex_unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>


            <span class="token comment" spellcheck="true">// check if last job</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">2</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>jobs<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token constant">NULL</span> <span class="token operator">&amp;&amp;</span> jobs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-></span>num <span class="token operator">>=</span> run_config<span class="token punctuation">.</span>record_num<span class="token punctuation">)</span><span class="token punctuation">{</span>
                    job <span class="token operator">=</span> jobs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
                    merge <span class="token operator">=</span> false<span class="token punctuation">,</span> last_job <span class="token operator">=</span> true<span class="token punctuation">;</span><span class="token punctuation">;</span>
                    <span class="token keyword">break</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token comment" spellcheck="true">// 结束线程</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>giveup<span class="token punctuation">)</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>merge<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment" spellcheck="true">// 归并排序</span>
            <span class="token keyword">int</span> sum <span class="token operator">=</span> jobs<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">-></span>num <span class="token operator">+</span> jobs<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-></span>num<span class="token punctuation">;</span>
            job <span class="token operator">=</span> <span class="token function">sort_job_init</span><span class="token punctuation">(</span>MERGE_SORT<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> sum<span class="token punctuation">,</span> false<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

            record_t <span class="token operator">*</span>temp_records <span class="token operator">=</span> <span class="token punctuation">(</span>record_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>record_t<span class="token punctuation">)</span> <span class="token operator">*</span> job<span class="token operator">-></span>num<span class="token punctuation">)</span><span class="token punctuation">;</span>
            job<span class="token operator">-></span>records <span class="token operator">=</span> <span class="token punctuation">(</span>record_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>record_t<span class="token punctuation">)</span> <span class="token operator">*</span> job<span class="token operator">-></span>num<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> ptr <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">2</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
                <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> jobs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-></span>num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
                    temp_records<span class="token punctuation">[</span>ptr<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> jobs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-></span>records<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">order_merge</span><span class="token punctuation">(</span>temp_records<span class="token punctuation">,</span> job<span class="token operator">-></span>records<span class="token punctuation">,</span> job<span class="token operator">-></span>num<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> jobs<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">-></span>num<span class="token punctuation">,</span> job<span class="token operator">-></span>num<span class="token punctuation">,</span> jobs<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">-></span>reverse<span class="token punctuation">)</span><span class="token punctuation">)</span>
                <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"merge error!"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment" spellcheck="true">// release job if job is merged by merge_worker</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">2</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>jobs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-></span>filename <span class="token operator">==</span> <span class="token constant">NULL</span><span class="token punctuation">)</span>
                    <span class="token function">sort_job_release</span><span class="token punctuation">(</span>jobs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token function">free</span><span class="token punctuation">(</span>temp_records<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment" spellcheck="true">// 将新的job插入到循环队列尾</span>
        pthread_t append_thd<span class="token punctuation">;</span>
        <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>append_thd<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> append_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span>job<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="D-主程序：启动消费者与生产者"><a href="#D-主程序：启动消费者与生产者" class="headerlink" title="D. 主程序：启动消费者与生产者"></a>D. 主程序：启动消费者与生产者</h4><p>最终，主程序内容如下：</p>
<ul>
<li>首先根据要排序的文件的字节数，推断需要的排序、合并线程数量（<code>init_config</code>完成），并写入到<code>run_config</code>中</li>
<li>初始化访问临界区需要的互斥锁<code>sorted_jobs_mutex</code>，信号量<code>sorted_jobs_cond</code></li>
<li>初始化<code>sorted_jobs</code>队列</li>
<li>启动<code>sort_worker</code>线程</li>
<li>启动<code>merge_worker</code>线程</li>
<li>等待<code>sort_worker</code>和<code>merge_worker</code>结束</li>
<li>从<code>sorted_jobs</code>中获取最后一个完成排序的<code>done_job</code></li>
<li>将<code>done_job</code>中的内容写入到输出文件中。</li>
</ul>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token keyword">int</span> argc<span class="token punctuation">,</span> <span class="token keyword">char</span> <span class="token operator">*</span>argv<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>argc <span class="token operator">!=</span> <span class="token number">3</span><span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"Empty input file"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    byteStream_t buffer<span class="token punctuation">;</span>

    <span class="token comment" spellcheck="true">// Code for parallel sort</span>
    <span class="token keyword">struct</span> timezone tz<span class="token punctuation">;</span>
    <span class="token keyword">struct</span> timeval start<span class="token punctuation">,</span> end<span class="token punctuation">;</span>
    <span class="token function">gettimeofday</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>start<span class="token punctuation">,</span> <span class="token operator">&amp;</span>tz<span class="token punctuation">)</span><span class="token punctuation">;</span>


    <span class="token comment" spellcheck="true">// init all</span>
    <span class="token keyword">int</span> byte <span class="token operator">=</span> <span class="token function">read_records</span><span class="token punctuation">(</span>argv<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>buffer<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">init_config</span><span class="token punctuation">(</span>byte<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_mutex_init</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_cond_init</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    sorted_jobs <span class="token operator">=</span> <span class="token punctuation">(</span>sort_job_t<span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>sort_job_t<span class="token operator">*</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token punctuation">(</span>run_config<span class="token punctuation">.</span>sorted_job_num<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    pthread_t <span class="token operator">*</span>sort_thread_pool <span class="token operator">=</span> <span class="token punctuation">(</span>pthread_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>pthread_t<span class="token punctuation">)</span> <span class="token operator">*</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">)</span><span class="token punctuation">;</span>


    <span class="token comment" spellcheck="true">// start sort threads</span>
    <span class="token keyword">int</span> seek <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> record_left <span class="token operator">=</span> run_config<span class="token punctuation">.</span>record_num<span class="token punctuation">;</span>
    <span class="token keyword">int</span> all <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    sort_job_t <span class="token operator">*</span><span class="token operator">*</span>jobs <span class="token operator">=</span> <span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span><span class="token punctuation">)</span> <span class="token operator">*</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">int</span> num <span class="token operator">=</span> run_config<span class="token punctuation">.</span>record_per_thread<span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">==</span> run_config<span class="token punctuation">.</span>sort_thread_num <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            num <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
            all <span class="token operator">+</span><span class="token operator">=</span> record_left<span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> 
            all <span class="token operator">+</span><span class="token operator">=</span> num<span class="token punctuation">;</span>
        jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">sort_job_init</span><span class="token punctuation">(</span>MERGE_SORT<span class="token punctuation">,</span> seek<span class="token punctuation">,</span> num<span class="token punctuation">,</span> false<span class="token punctuation">,</span> argv<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sort_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> sort_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span>jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        seek <span class="token operator">+</span><span class="token operator">=</span> num<span class="token punctuation">;</span>
        record_left <span class="token operator">-</span><span class="token operator">=</span> num<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment" spellcheck="true">// start merge threads</span>
    bool wait_arg <span class="token operator">=</span> true<span class="token punctuation">;</span>
    bool timeout_arg <span class="token operator">=</span> false<span class="token punctuation">;</span>
    pthread_t <span class="token operator">*</span>merge_thread_pool <span class="token operator">=</span> <span class="token punctuation">(</span>pthread_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>pthread_t<span class="token punctuation">)</span> <span class="token operator">*</span> run_config<span class="token punctuation">.</span>merge_thread_num<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>merge_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
            <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>merge_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> merge_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>wait_arg<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span>
            <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>merge_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> merge_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>timeout_arg<span class="token punctuation">)</span><span class="token punctuation">;</span>


    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token function">pthread_join</span><span class="token punctuation">(</span>sort_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>merge_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token function">pthread_join</span><span class="token punctuation">(</span>merge_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>


    <span class="token comment" spellcheck="true">// get done_job</span>
    <span class="token function">pthread_mutex_lock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 等待producer</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">is_empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token function">pthread_cond_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">,</span> <span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    sort_job_t<span class="token operator">*</span> done_job <span class="token operator">=</span> <span class="token function">do_get</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 唤醒consumer</span>
    <span class="token function">pthread_cond_signal</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_mutex_unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>


    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">write_records</span><span class="token punctuation">(</span>argv<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span> done_job<span class="token punctuation">)</span> <span class="token operator">!=</span> byte<span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"read record and write record mismatch"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>PRINTKEY <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Main, Thd -> %d: %s\n"</span><span class="token punctuation">,</span> j<span class="token punctuation">,</span> func_name<span class="token punctuation">[</span>jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-></span>sort_func<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"After Sorts:\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token function">printKeys</span><span class="token punctuation">(</span>jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-></span>records<span class="token punctuation">,</span> jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-></span>num<span class="token punctuation">)</span><span class="token punctuation">;</span>
            delim<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>PRINTKEY <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Main, After Merge:\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">// 下面因为要访问共享资源sorted_jobs，所以都是临界区</span>
        <span class="token function">printKeys</span><span class="token punctuation">(</span>done_job<span class="token operator">-></span>records<span class="token punctuation">,</span> done_job<span class="token operator">-></span>num<span class="token punctuation">)</span><span class="token punctuation">;</span>
        delim<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">gettimeofday</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>end<span class="token punctuation">,</span> <span class="token operator">&amp;</span>tz<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> sec <span class="token operator">=</span> end<span class="token punctuation">.</span>tv_sec <span class="token operator">-</span> start<span class="token punctuation">.</span>tv_sec<span class="token punctuation">;</span>
    <span class="token keyword">int</span> usec <span class="token operator">=</span> end<span class="token punctuation">.</span>tv_usec <span class="token operator">-</span> start<span class="token punctuation">.</span>tv_usec<span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>usec <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        sec <span class="token operator">-</span><span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
        usec <span class="token operator">+</span><span class="token operator">=</span> <span class="token number">1000000</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">float</span> used <span class="token operator">=</span> sec <span class="token operator">+</span> usec <span class="token operator">/</span> <span class="token number">1000000.0</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Main, sort %d records, using %.6f seconds\n"</span><span class="token punctuation">,</span> run_config<span class="token punctuation">.</span>record_num<span class="token punctuation">,</span> used<span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="E-总结"><a href="#E-总结" class="headerlink" title="E. 总结"></a>E. 总结</h4><p>总的来说，该多线程模型并不要求必须要先等所有的<code>sort_worker</code>排序完再合并，也不要求只能有一个<code>merge_worker</code>进行合并，支持并行的排序以及合并，<strong>因此理论上性能比较高</strong>。</p>
<p>Debug难度较大，两个死锁改了一整天。</p>
<h3 id="6-拾遗"><a href="#6-拾遗" class="headerlink" title="6. 拾遗"></a>6. 拾遗</h3><p>最后就是一些小工具</p>
<h4 id="A-write-record函数"><a href="#A-write-record函数" class="headerlink" title="A. write_record函数"></a>A. write_record函数</h4><p>在经过<code>merge_worker</code>合并得到最后一个<code>sorted_job</code>后，需要将排序后的内容写回到文件中，因此提供了<code>write_record</code>函数</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 * @brief 将job中的record写入到filename中
 * 
 * @param filename 要写入的文件的文件名
 * @param job 要写入的job的名称
 * @return int 
 */</span>
<span class="token keyword">int</span> <span class="token function">write_records</span><span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> filename<span class="token punctuation">,</span> sort_job_t<span class="token operator">*</span>job<span class="token punctuation">)</span><span class="token punctuation">{</span>
    FILE <span class="token operator">*</span>bin_file <span class="token operator">=</span> <span class="token function">fopen</span><span class="token punctuation">(</span>filename<span class="token punctuation">,</span> <span class="token string">"wb"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>bin_file <span class="token operator">==</span> <span class="token constant">NULL</span><span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"file open error"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">int</span> writte_byte <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> job<span class="token operator">-></span>num<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">fwrite</span><span class="token punctuation">(</span><span class="token operator">*</span><span class="token punctuation">(</span>job<span class="token operator">-></span>records<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> BYTE_PER_RECORD<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> bin_file<span class="token punctuation">)</span> <span class="token operator">!=</span> <span class="token number">1</span><span class="token punctuation">)</span>
            <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"record write error"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        writte_byte <span class="token operator">+</span><span class="token operator">=</span> BYTE_PER_RECORD<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> writte_byte<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="B-psort-error函数"><a href="#B-psort-error函数" class="headerlink" title="B. psort_error函数"></a>B. psort_error函数</h4><p>在开发阶段，为了能够输出错误信息，因此使用<code>psort_error</code>函数。相比于单纯的使用<code>fprintf(stderr, "Error")</code>来说，<code>psort_error</code>可以根据是否为调试阶段有不同的表现：</p>
<ul>
<li><code>DEBUG</code>阶段：输出出错的行数，以及错误信息</li>
<li>非<code>DEBUG</code>阶段：输出<code>An error has occurred!</code></li>
</ul>
<p>输出行号的实现则是通过宏函数以及编译器内置的<code>__LINE__</code>变量实现。</p>
<p>具体实现如下</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token macro property">#<span class="token directive keyword">define</span> psort_error(s) _psort_error(s, __LINE__)</span>

<span class="token comment" spellcheck="true">/**
 * @brief _psort_error用于输出错误信息，若定义DEBUG宏则输出错误行号, 和posort_error宏函数搭配使用
 * 
 * @param str 错误信息
 * @param lineno 错误发生的行号
 * 
 * @author Shihong Wang
 * @date 2022.10.29
 */</span>
<span class="token keyword">void</span> <span class="token function">_psort_error</span><span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span>str<span class="token punctuation">,</span> <span class="token keyword">int</span> lineno<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">char</span> <span class="token operator">*</span>str_c<span class="token punctuation">;</span>
<span class="token macro property">#<span class="token directive keyword">ifdef</span> DEBUG</span>
    <span class="token comment" spellcheck="true">// int to alphabetic-number</span>
    <span class="token keyword">char</span> line<span class="token punctuation">[</span><span class="token number">20</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token function">sprintf</span><span class="token punctuation">(</span>line<span class="token punctuation">,</span> <span class="token string">"line: %d, "</span><span class="token punctuation">,</span> lineno<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">//  construct str</span>
    str_c <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token punctuation">(</span><span class="token function">strlen</span><span class="token punctuation">(</span>str<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>line<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">sprintf</span><span class="token punctuation">(</span>str_c<span class="token punctuation">,</span> <span class="token string">"%s"</span><span class="token punctuation">,</span> line<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">sprintf</span><span class="token punctuation">(</span>str_c <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>line<span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token string">"%s"</span><span class="token punctuation">,</span> str<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%s\n"</span><span class="token punctuation">,</span> str_c<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">exit</span><span class="token punctuation">(</span>EXIT_FAILURE<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token macro property">#<span class="token directive keyword">else</span></span>
    <span class="token function">fprintf</span><span class="token punctuation">(</span><span class="token constant">stderr</span><span class="token punctuation">,</span> <span class="token string">"An error has occurred\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">exit</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token macro property">#<span class="token directive keyword">endif</span></span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-printKeys函数"><a href="#C-printKeys函数" class="headerlink" title="C. printKeys函数"></a>C. printKeys函数</h4><p>开发的时候方便调试，输出<code>record</code>数组中所有<code>record</code>的<code>key</code></p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">/**
 *
 * @param records record数组
 * @param num record数组中的record数量
 *
 * @author Shihong Wang
 * @date 2022.10.30
 */</span>
<span class="token keyword">void</span> <span class="token function">printKeys</span><span class="token punctuation">(</span>record_t records<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> num<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token constant">NULL</span> <span class="token operator">==</span> records<span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"record is NULL, did not malloc records? Or worker thread didn't run first?"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> num<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%4d -> %11d\n"</span><span class="token punctuation">,</span> i<span class="token punctuation">,</span> <span class="token function">get_key</span><span class="token punctuation">(</span>records<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-benchmark"><a href="#C-benchmark" class="headerlink" title="C. benchmark"></a>C. benchmark</h4><p>为了通过比较选择速度最快的排序算法，因此主程序中通过定义<code>BENCHMARK</code>宏来测试不同排序算法的性能</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token keyword">int</span> argc<span class="token punctuation">,</span> <span class="token keyword">char</span> <span class="token operator">*</span>argv<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>argc <span class="token operator">!=</span> <span class="token number">3</span><span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"Empty input file"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    byteStream_t buffer<span class="token punctuation">;</span>

<span class="token macro property">#<span class="token directive keyword">ifdef</span> BENCHMARK</span>
    <span class="token comment" spellcheck="true">// Code for benchmark</span>
    clock_t start<span class="token punctuation">,</span> end<span class="token punctuation">;</span>

    <span class="token keyword">int</span> byte <span class="token operator">=</span> <span class="token function">read_records</span><span class="token punctuation">(</span>argv<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>buffer<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Test file: %s\n"</span><span class="token punctuation">,</span> argv<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%s -> %d bytes\n"</span><span class="token punctuation">,</span> argv<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> byte<span class="token punctuation">)</span><span class="token punctuation">;</span>
    delim<span class="token punctuation">;</span>
    record_t <span class="token operator">*</span>records<span class="token punctuation">;</span>
    <span class="token keyword">int</span> num <span class="token operator">=</span> <span class="token function">parse_records</span><span class="token punctuation">(</span>buffer<span class="token punctuation">,</span> <span class="token operator">&amp;</span>records<span class="token punctuation">,</span> byte<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span>sort_func<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span>sort_func<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Benchmark: %s\n"</span><span class="token punctuation">,</span> func_name<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        start <span class="token operator">=</span> <span class="token function">clock</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        sort_func<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> num<span class="token punctuation">,</span> false<span class="token punctuation">)</span><span class="token punctuation">;</span>
        end <span class="token operator">=</span> <span class="token function">clock</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>PRINTKEY <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"After Sorts:\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token function">printKeys</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> num<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Sort time used: %4f seconds\n"</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">double</span><span class="token punctuation">)</span><span class="token punctuation">(</span>end <span class="token operator">-</span> start<span class="token punctuation">)</span> <span class="token operator">/</span> CLOCKS_PER_SEC<span class="token punctuation">)</span><span class="token punctuation">;</span>
        delim<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token macro property">#<span class="token directive keyword">endif</span></span>
        <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>因此，最终主程序为</p>
<pre class="line-numbers language-c"><code class="language-c"><span class="token comment" spellcheck="true">// #define BENCHMARK</span>
<span class="token macro property">#<span class="token directive keyword">define</span> MAIN</span>
<span class="token macro property">#<span class="token directive keyword">define</span> PRINTKEY 0</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token keyword">int</span> argc<span class="token punctuation">,</span> <span class="token keyword">char</span> <span class="token operator">*</span>argv<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>argc <span class="token operator">!=</span> <span class="token number">3</span><span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"Empty input file"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    byteStream_t buffer<span class="token punctuation">;</span>

<span class="token macro property">#<span class="token directive keyword">ifdef</span> BENCHMARK</span>
    <span class="token comment" spellcheck="true">// Code for benchmark</span>
    clock_t start<span class="token punctuation">,</span> end<span class="token punctuation">;</span>

    <span class="token keyword">int</span> byte <span class="token operator">=</span> <span class="token function">read_records</span><span class="token punctuation">(</span>argv<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>buffer<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Test file: %s\n"</span><span class="token punctuation">,</span> argv<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%s -> %d bytes\n"</span><span class="token punctuation">,</span> argv<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> byte<span class="token punctuation">)</span><span class="token punctuation">;</span>
    delim<span class="token punctuation">;</span>
    record_t <span class="token operator">*</span>records<span class="token punctuation">;</span>
    <span class="token keyword">int</span> num <span class="token operator">=</span> <span class="token function">parse_records</span><span class="token punctuation">(</span>buffer<span class="token punctuation">,</span> <span class="token operator">&amp;</span>records<span class="token punctuation">,</span> byte<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span>sort_func<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span>sort_func<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Benchmark: %s\n"</span><span class="token punctuation">,</span> func_name<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        start <span class="token operator">=</span> <span class="token function">clock</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        sort_func<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> num<span class="token punctuation">,</span> false<span class="token punctuation">)</span><span class="token punctuation">;</span>
        end <span class="token operator">=</span> <span class="token function">clock</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>PRINTKEY <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"After Sorts:\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token function">printKeys</span><span class="token punctuation">(</span>records<span class="token punctuation">,</span> num<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Sort time used: %4f seconds\n"</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">double</span><span class="token punctuation">)</span><span class="token punctuation">(</span>end <span class="token operator">-</span> start<span class="token punctuation">)</span> <span class="token operator">/</span> CLOCKS_PER_SEC<span class="token punctuation">)</span><span class="token punctuation">;</span>
        delim<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token macro property">#<span class="token directive keyword">endif</span></span>

<span class="token macro property">#<span class="token directive keyword">ifdef</span> MAIN</span>
    <span class="token comment" spellcheck="true">// Code for parallel sort</span>
    <span class="token keyword">struct</span> timezone tz<span class="token punctuation">;</span>
    <span class="token keyword">struct</span> timeval start<span class="token punctuation">,</span> end<span class="token punctuation">;</span>
    <span class="token function">gettimeofday</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>start<span class="token punctuation">,</span> <span class="token operator">&amp;</span>tz<span class="token punctuation">)</span><span class="token punctuation">;</span>


    <span class="token comment" spellcheck="true">// init all</span>
    <span class="token keyword">int</span> byte <span class="token operator">=</span> <span class="token function">read_records</span><span class="token punctuation">(</span>argv<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>buffer<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">init_config</span><span class="token punctuation">(</span>byte<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_mutex_init</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_cond_init</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    sorted_jobs <span class="token operator">=</span> <span class="token punctuation">(</span>sort_job_t<span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>sort_job_t<span class="token operator">*</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token punctuation">(</span>run_config<span class="token punctuation">.</span>sorted_job_num<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    pthread_t <span class="token operator">*</span>sort_thread_pool <span class="token operator">=</span> <span class="token punctuation">(</span>pthread_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>pthread_t<span class="token punctuation">)</span> <span class="token operator">*</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">)</span><span class="token punctuation">;</span>

<span class="token macro property">#<span class="token directive keyword">ifdef</span> DEBUG</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Test file: %s\n"</span><span class="token punctuation">,</span> argv<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%s -> %d bytes, %d records\n"</span><span class="token punctuation">,</span> argv<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> byte<span class="token punctuation">,</span> run_config<span class="token punctuation">.</span>record_num<span class="token punctuation">)</span><span class="token punctuation">;</span>
    delim<span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Sort thread: %d, %d records per thread\n"</span><span class="token punctuation">,</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">,</span> run_config<span class="token punctuation">.</span>record_per_thread<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Merge thread: %d\n"</span><span class="token punctuation">,</span> run_config<span class="token punctuation">.</span>merge_thread_num<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Sorted job: %d\n"</span><span class="token punctuation">,</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">)</span><span class="token punctuation">;</span>
    delim<span class="token punctuation">;</span>
<span class="token macro property">#<span class="token directive keyword">endif</span></span>

    <span class="token comment" spellcheck="true">// start sort threads</span>
    <span class="token keyword">int</span> seek <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> record_left <span class="token operator">=</span> run_config<span class="token punctuation">.</span>record_num<span class="token punctuation">;</span>
    <span class="token keyword">int</span> all <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    sort_job_t <span class="token operator">*</span><span class="token operator">*</span>jobs <span class="token operator">=</span> <span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>sort_job_t <span class="token operator">*</span><span class="token punctuation">)</span> <span class="token operator">*</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">int</span> num <span class="token operator">=</span> run_config<span class="token punctuation">.</span>record_per_thread<span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">==</span> run_config<span class="token punctuation">.</span>sort_thread_num <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            num <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
            all <span class="token operator">+</span><span class="token operator">=</span> record_left<span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> 
            all <span class="token operator">+</span><span class="token operator">=</span> num<span class="token punctuation">;</span>
        jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">sort_job_init</span><span class="token punctuation">(</span>MERGE_SORT<span class="token punctuation">,</span> seek<span class="token punctuation">,</span> num<span class="token punctuation">,</span> false<span class="token punctuation">,</span> argv<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sort_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> sort_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span>jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        seek <span class="token operator">+</span><span class="token operator">=</span> num<span class="token punctuation">;</span>
        record_left <span class="token operator">-</span><span class="token operator">=</span> num<span class="token punctuation">;</span>
<span class="token macro property">#<span class="token directive keyword">ifdef</span> DEBUG</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Sort thread %d:\n"</span><span class="token punctuation">,</span> j<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"sort func %d -> %s\n"</span><span class="token punctuation">,</span> jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-></span>sort_func<span class="token punctuation">,</span> func_name<span class="token punctuation">[</span>jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-></span>sort_func<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"seek -> %d, num -> %d\n"</span><span class="token punctuation">,</span> jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-></span>seek<span class="token punctuation">,</span> jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-></span>num<span class="token punctuation">)</span><span class="token punctuation">;</span>
        delim<span class="token punctuation">;</span>
<span class="token macro property">#<span class="token directive keyword">endif</span></span>
    <span class="token punctuation">}</span>
<span class="token macro property">#<span class="token directive keyword">ifdef</span> DEBUG</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"All allocated records: %d\n"</span><span class="token punctuation">,</span> all<span class="token punctuation">)</span><span class="token punctuation">;</span>
    delim<span class="token punctuation">;</span>
<span class="token macro property">#<span class="token directive keyword">endif</span></span>

    <span class="token comment" spellcheck="true">// start merge threads</span>
    bool wait_arg <span class="token operator">=</span> true<span class="token punctuation">;</span>
    bool timeout_arg <span class="token operator">=</span> false<span class="token punctuation">;</span>
    pthread_t <span class="token operator">*</span>merge_thread_pool <span class="token operator">=</span> <span class="token punctuation">(</span>pthread_t <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>pthread_t<span class="token punctuation">)</span> <span class="token operator">*</span> run_config<span class="token punctuation">.</span>merge_thread_num<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>merge_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
            <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>merge_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> merge_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>wait_arg<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span>
            <span class="token function">pthread_create</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>merge_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">,</span> merge_worker<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token operator">&amp;</span>timeout_arg<span class="token punctuation">)</span><span class="token punctuation">;</span>


    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token function">pthread_join</span><span class="token punctuation">(</span>sort_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>merge_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token function">pthread_join</span><span class="token punctuation">(</span>merge_thread_pool<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">;</span>


    <span class="token comment" spellcheck="true">// get done_job</span>
    <span class="token function">pthread_mutex_lock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 等待producer</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">is_empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token function">pthread_cond_wait</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">,</span> <span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    sort_job_t<span class="token operator">*</span> done_job <span class="token operator">=</span> <span class="token function">do_get</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// 唤醒consumer</span>
    <span class="token function">pthread_cond_signal</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_cond<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">pthread_mutex_unlock</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>sorted_jobs_mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>

<span class="token macro property">#<span class="token directive keyword">ifdef</span> DEBUG</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Finished, %d records sorted!\n"</span><span class="token punctuation">,</span> all<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Writing...\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token macro property">#<span class="token directive keyword">endif</span></span>

    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">write_records</span><span class="token punctuation">(</span>argv<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span> done_job<span class="token punctuation">)</span> <span class="token operator">!=</span> byte<span class="token punctuation">)</span>
        <span class="token function">psort_error</span><span class="token punctuation">(</span><span class="token string">"read record and write record mismatch"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> run_config<span class="token punctuation">.</span>sort_thread_num<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>PRINTKEY <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Main, Thd -> %d: %s\n"</span><span class="token punctuation">,</span> j<span class="token punctuation">,</span> func_name<span class="token punctuation">[</span>jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-></span>sort_func<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"After Sorts:\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token function">printKeys</span><span class="token punctuation">(</span>jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-></span>records<span class="token punctuation">,</span> jobs<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-></span>num<span class="token punctuation">)</span><span class="token punctuation">;</span>
            delim<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>PRINTKEY <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Main, After Merge:\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">// 下面因为要访问共享资源sorted_jobs，所以都是临界区</span>
        <span class="token function">printKeys</span><span class="token punctuation">(</span>done_job<span class="token operator">-></span>records<span class="token punctuation">,</span> done_job<span class="token operator">-></span>num<span class="token punctuation">)</span><span class="token punctuation">;</span>
        delim<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">gettimeofday</span><span class="token punctuation">(</span><span class="token operator">&amp;</span>end<span class="token punctuation">,</span> <span class="token operator">&amp;</span>tz<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> sec <span class="token operator">=</span> end<span class="token punctuation">.</span>tv_sec <span class="token operator">-</span> start<span class="token punctuation">.</span>tv_sec<span class="token punctuation">;</span>
    <span class="token keyword">int</span> usec <span class="token operator">=</span> end<span class="token punctuation">.</span>tv_usec <span class="token operator">-</span> start<span class="token punctuation">.</span>tv_usec<span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>usec <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        sec <span class="token operator">-</span><span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
        usec <span class="token operator">+</span><span class="token operator">=</span> <span class="token number">1000000</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">float</span> used <span class="token operator">=</span> sec <span class="token operator">+</span> usec <span class="token operator">/</span> <span class="token number">1000000.0</span><span class="token punctuation">;</span>
    <span class="token comment" spellcheck="true">// printf("Main, sort %d records, using %.6f seconds\n", run_config.record_num, used);</span>
<span class="token macro property">#<span class="token directive keyword">endif</span></span>

    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="项目代码"><a href="#项目代码" class="headerlink" title="项目代码"></a>项目代码</h2><p>代码已开源：<a target="_blank" rel="noopener" href="https://github.com/jackwang0108/CS537-Project3.git">https://github.com/jackwang0108/CS537-Project3.git</a></p>
<h3 id="1-项目结构"><a href="#1-项目结构" class="headerlink" title="1. 项目结构"></a>1. 项目结构</h3><p>项目结构如下</p>
<pre class="line-numbers language-bash"><code class="language-bash">tree -C ./
<span aria-hidden="true" class="line-numbers-rows"><span></span></span></code></pre>
<p>其中：</p>
<ul>
<li><code>CMakeLists.txt</code>组织项目</li>
<li><code>tools</code>文件中存放了工具脚本，包括生成用于测试的包含<code>record</code>二进制文件的<code>gentest.sh</code>，自动构建项目的<code>autobuild.sh</code>，自动测试的<code>autotest.sh</code>，以及按顺序输出二进制文件所有<code>record</code>的<code>key</code>的<code>printkey.sh</code></li>
<li>程序源码为<code>libpsort.h</code>、<code>libpsort.c</code>、<code>main.c</code>，<code>gentest.c</code>和<code>printkey.c</code>为工具程序</li>
</ul>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221109044515531.png" alt="项目结构"></p>
<h3 id="2-使用说明"><a href="#2-使用说明" class="headerlink" title="2. 使用说明"></a>2. 使用说明</h3><h4 id="A-初始化项目"><a href="#A-初始化项目" class="headerlink" title="A. 初始化项目"></a>A. 初始化项目</h4><p>使用在项目根目录下的<code>init.sh</code>初始化项目</p>
<pre class="line-numbers language-bash"><code class="language-bash"><span class="token function">cd</span> <span class="token operator">&lt;</span>path-to-project<span class="token operator">></span>
<span class="token function">source</span> init.sh
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span></span></code></pre>
<h4 id="B-编译"><a href="#B-编译" class="headerlink" title="B. 编译"></a>B. 编译</h4><p>可以手动编译</p>
<pre class="line-numbers language-bash"><code class="language-bash"><span class="token function">cd</span> <span class="token operator">&lt;</span>path-to-project<span class="token operator">></span>
<span class="token function">mkdir</span> build
<span class="token function">cd</span> build
cmake <span class="token punctuation">..</span>
<span class="token function">make</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>或者在<code>source init.sh</code>后使用提供的自动编译工具</p>
<pre class="line-numbers language-bash"><code class="language-bash"><span class="token function">source</span> init.sh
autobuild.sh
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span></span></code></pre>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221109045433994.png" alt="自动编译"></p>
<p>编译后将得到<code>libppsort.a</code>库和可执行文件，分别位于<code>lib</code>文件夹和<code>bin</code>文件夹下</p>
<pre class="line-numbers language-bash"><code class="language-bash">tree -C -I build
<span aria-hidden="true" class="line-numbers-rows"><span></span></span></code></pre>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221109045639062.png" alt="编译后得到可执行文件"></p>
<h4 id="C-测试"><a href="#C-测试" class="headerlink" title="C. 测试"></a>C. 测试</h4><p>使用<code>gentest.sh</code>生成测试文件。这里指定生成100个record</p>
<pre class="line-numbers language-bash"><code class="language-bash"><span class="token function">source</span> init.sh
gentest.sh 10
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span></span></code></pre>
<p>测试文件将写入<code>&lt;path-toprojec&gt;/test.bin文件中</code></p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221109050250292.png" alt="生成测试文件"></p>
<p>而后使用<code>printkey</code>程序查看其中每个<code>record</code>的键值</p>
<pre class="line-numbers language-bash"><code class="language-bash">./bin/printkey test.bin
<span aria-hidden="true" class="line-numbers-rows"><span></span></span></code></pre>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221109050330618.png" alt="查看测试文件key值"></p>
<p>使用测试脚本<code>autotest.sh</code>进行测试，测试后的结果将写入<code>sorted.bin</code>中</p>
<pre class="line-numbers language-bash"><code class="language-bash">autotest.sh
<span aria-hidden="true" class="line-numbers-rows"><span></span></span></code></pre>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221109050430623.png" alt="进行测试"></p>
<p>最后，查看排序后的结果</p>
<pre class="line-numbers language-bash"><code class="language-bash">./bin/printkey sorted.bin
<span aria-hidden="true" class="line-numbers-rows"><span></span></span></code></pre>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221109050527197.png" alt="查看排序后的结果"></p>
<h3 id="3-性能测试"><a href="#3-性能测试" class="headerlink" title="3. 性能测试"></a>3. 性能测试</h3><p>使用<code>gentest.sh</code>生成10,000,000（一百万个record），文件大小954M。对其进行排序</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221109050741114.png" alt="性能测试"></p>
<p>使用time进行计时</p>
<pre class="line-numbers language-bash"><code class="language-bash"><span class="token function">time</span> ./bin/psort test.bin sorted.bin
<span aria-hidden="true" class="line-numbers-rows"><span></span></span></code></pre>
<p>包含将排序后文件写入到<code>sorted.bin</code>中，一共用时<code>8.574</code>秒，平均每秒处理十万个<code>record</code></p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221109050910881.png" alt="计时"></p>

                
            </div>
            <hr/>

            

    <div class="reprint" id="reprint-statement">
        
            <div class="reprint__author">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-user">
                        文章作者:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="/about" rel="external nofollow noreferrer">Jack Wang</a>
                </span>
            </div>
            <div class="reprint__type">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-link">
                        文章链接:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="https://jackwang0107.github.io/2022/11/08/parallel-sort/">https://jackwang0107.github.io/2022/11/08/parallel-sort/</a>
                </span>
            </div>
            <div class="reprint__notice">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-copyright">
                        版权声明:
                    </i>
                </span>
                <span class="reprint-info">
                    本博客所有文章除特別声明外，均采用
                    <a href="https://creativecommons.org/licenses/by/4.0/deed.zh" rel="external nofollow noreferrer" target="_blank">CC BY 4.0</a>
                    许可协议。转载请注明来源
                    <a href="/about" target="_blank">Jack Wang</a>
                    !
                </span>
            </div>
        
    </div>

    <script async defer>
      document.addEventListener("copy", function (e) {
        let toastHTML = '<span>复制成功，请遵循本文的转载规则</span><button class="btn-flat toast-action" onclick="navToReprintStatement()" style="font-size: smaller">查看</a>';
        M.toast({html: toastHTML})
      });

      function navToReprintStatement() {
        $("html, body").animate({scrollTop: $("#reprint-statement").offset().top - 80}, 800);
      }
    </script>



            <div class="tag_share" style="display: block;">
                <div class="post-meta__tag-list" style="display: inline-block;">
                    
                        <div class="article-tag">
                            
                                <a href="/tags/C%E8%AF%AD%E8%A8%80/">
                                    <span class="chip bg-color">C语言</span>
                                </a>
                            
                                <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/">
                                    <span class="chip bg-color">数据结构和算法</span>
                                </a>
                            
                                <a href="/tags/%E5%A4%9A%E7%BA%BF%E7%A8%8B/">
                                    <span class="chip bg-color">多线程</span>
                                </a>
                            
                                <a href="/tags/%E5%90%8C%E6%AD%A5%E4%B8%8E%E4%BA%92%E6%96%A5/">
                                    <span class="chip bg-color">同步与互斥</span>
                                </a>
                            
                        </div>
                    
                </div>
                <div class="post_share" style="zoom: 80%; width: fit-content; display: inline-block; float: right; margin: -0.15rem 0;">
                    <link rel="stylesheet" type="text/css" href="/libs/share/css/share.min.css">
<div id="article-share">

    
    <div class="social-share" data-sites="twitter,facebook,google,qq,qzone,wechat,weibo,douban,linkedin" data-wechat-qrcode-helper="<p>微信扫一扫即可分享！</p>"></div>
    <script src="/libs/share/js/social-share.min.js"></script>
    

    

</div>

                </div>
            </div>
            
                <style>
    #reward {
        margin: 40px 0;
        text-align: center;
    }

    #reward .reward-link {
        font-size: 1.4rem;
        line-height: 38px;
    }

    #reward .btn-floating:hover {
        box-shadow: 0 6px 12px rgba(0, 0, 0, 0.2), 0 5px 15px rgba(0, 0, 0, 0.2);
    }

    #rewardModal {
        width: 320px;
        height: 350px;
    }

    #rewardModal .reward-title {
        margin: 15px auto;
        padding-bottom: 5px;
    }

    #rewardModal .modal-content {
        padding: 10px;
    }

    #rewardModal .close {
        position: absolute;
        right: 15px;
        top: 15px;
        color: rgba(0, 0, 0, 0.5);
        font-size: 1.3rem;
        line-height: 20px;
        cursor: pointer;
    }

    #rewardModal .close:hover {
        color: #ef5350;
        transform: scale(1.3);
        -moz-transform:scale(1.3);
        -webkit-transform:scale(1.3);
        -o-transform:scale(1.3);
    }

    #rewardModal .reward-tabs {
        margin: 0 auto;
        width: 210px;
    }

    .reward-tabs .tabs {
        height: 38px;
        margin: 10px auto;
        padding-left: 0;
    }

    .reward-content ul {
        padding-left: 0 !important;
    }

    .reward-tabs .tabs .tab {
        height: 38px;
        line-height: 38px;
    }

    .reward-tabs .tab a {
        color: #fff;
        background-color: #ccc;
    }

    .reward-tabs .tab a:hover {
        background-color: #ccc;
        color: #fff;
    }

    .reward-tabs .wechat-tab .active {
        color: #fff !important;
        background-color: #22AB38 !important;
    }

    .reward-tabs .alipay-tab .active {
        color: #fff !important;
        background-color: #019FE8 !important;
    }

    .reward-tabs .reward-img {
        width: 210px;
        height: 210px;
    }
</style>

<div id="reward">
    <a href="#rewardModal" class="reward-link modal-trigger btn-floating btn-medium waves-effect waves-light red">赏</a>

    <!-- Modal Structure -->
    <div id="rewardModal" class="modal">
        <div class="modal-content">
            <a class="close modal-close"><i class="fas fa-times"></i></a>
            <h4 class="reward-title">你的赏识是我前进的动力</h4>
            <div class="reward-content">
                <div class="reward-tabs">
                    <ul class="tabs row">
                        <li class="tab col s6 alipay-tab waves-effect waves-light"><a href="#alipay">支付宝</a></li>
                        <li class="tab col s6 wechat-tab waves-effect waves-light"><a href="#wechat">微 信</a></li>
                    </ul>
                    <div id="alipay">
                        <img src="/medias/reward/alipay.png" class="reward-img" alt="支付宝打赏二维码">
                    </div>
                    <div id="wechat">
                        <img src="/medias/reward/wechat.jpg" class="reward-img" alt="微信打赏二维码">
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>

<script>
    $(function () {
        $('.tabs').tabs();
    });
</script>

            
        </div>
    </div>

    

    

    

    

    

    

    

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="fas fa-chevron-left"></i>&nbsp;上一篇</div>
            <div class="card">
                <a href="/2022/11/09/bash-de-te-xing/">
                    <div class="card-image">
                        
                        <img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221109211256651.png" class="responsive-img" alt="Bash特性">
                        
                        <span class="card-title">Bash特性</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            本文主要介绍了Bash等解释器的特性
                        
                    </div>
                    <div class="publish-info">
                        <span class="publish-date">
                            <i class="far fa-clock fa-fw icon-date"></i>2022-11-09
                        </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/Linux%E5%AE%9E%E7%94%A8%E6%8A%80%E5%B7%A7/" class="post-category">
                                    Linux实用技巧
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/Linux/">
                        <span class="chip bg-color">Linux</span>
                    </a>
                    
                    <a href="/tags/Ubuntu/">
                        <span class="chip bg-color">Ubuntu</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                下一篇&nbsp;<i class="fas fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="/2022/10/29/tuo-fu-xue-xi/">
                    <div class="card-image">
                        
                        <img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/image-20221029220722902.png" class="responsive-img" alt="托福学习笔记">
                        
                        <span class="card-title">托福学习笔记</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            托福笔记，免得以后复习都要重新找
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="far fa-clock fa-fw icon-date"></i>2022-10-29
                            </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/%E8%8B%B1%E8%AF%AD%E5%AD%A6%E4%B9%A0/" class="post-category">
                                    英语学习
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/%E6%9D%82%E9%A1%B9/">
                        <span class="chip bg-color">杂项</span>
                    </a>
                    
                    <a href="/tags/%E8%8B%B1%E8%AF%AD%E5%AD%A6%E4%B9%A0/">
                        <span class="chip bg-color">英语学习</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>

</div>


<script>
    $('#articleContent').on('copy', function (e) {
        // IE8 or earlier browser is 'undefined'
        if (typeof window.getSelection === 'undefined') return;

        var selection = window.getSelection();
        // if the selection is short let's not annoy our users.
        if (('' + selection).length < Number.parseInt('120')) {
            return;
        }

        // create a div outside of the visible area and fill it with the selected text.
        var bodyElement = document.getElementsByTagName('body')[0];
        var newdiv = document.createElement('div');
        newdiv.style.position = 'absolute';
        newdiv.style.left = '-99999px';
        bodyElement.appendChild(newdiv);
        newdiv.appendChild(selection.getRangeAt(0).cloneContents());

        // we need a <pre> tag workaround.
        // otherwise the text inside "pre" loses all the line breaks!
        if (selection.getRangeAt(0).commonAncestorContainer.nodeName === 'PRE' || selection.getRangeAt(0).commonAncestorContainer.nodeName === 'CODE') {
            newdiv.innerHTML = "<pre>" + newdiv.innerHTML + "</pre>";
        }

        var url = document.location.href;
        newdiv.innerHTML += '<br />'
            + '来源: JackWang&#39;s Blog<br />'
            + '文章作者: Jack Wang<br />'
            + '文章链接: <a href="' + url + '">' + url + '</a><br />'
            + '本文章著作权归作者所有，任何形式的转载都请注明出处。';

        selection.selectAllChildren(newdiv);
        window.setTimeout(function () {bodyElement.removeChild(newdiv);}, 200);
    });
</script>


<!-- 代码块功能依赖 -->
<script type="text/javascript" src="/libs/codeBlock/codeBlockFuction.js"></script>

<!-- 代码语言 -->

<script type="text/javascript" src="/libs/codeBlock/codeLang.js"></script>


<!-- 代码块复制 -->

<script type="text/javascript" src="/libs/codeBlock/codeCopy.js"></script>


<!-- 代码块收缩 -->

<script type="text/javascript" src="/libs/codeBlock/codeShrink.js"></script>


    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget card" style="background-color: white;">
            <div class="toc-title"><i class="far fa-list-alt"></i>&nbsp;&nbsp;目录</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fas fa-list-ul"></i>
    </a>
</div>


<script src="/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            collapseDepth: Number('2'),
            headingSelector: 'h1, h2, h3, h4, h5, h6'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h1, h2, h3, h4, h5, h6').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).hide();
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).show();
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>

    

</main>




    <footer class="page-footer bg-color">
    

    <div class="container row center-align"
         style="margin-bottom: 15px !important;">
        <div class="col s12 m8 l8 copy-right">
            Copyright&nbsp;&copy;
            
                <span id="year">2021-2023</span>
            
            <a href="/about" target="_blank">Jack Wang</a>
            <!-- |&nbsp;Powered by&nbsp;<a href="https://hexo.io/" target="_blank">Hexo</a> -->
            <!-- |&nbsp;Theme&nbsp;<a href="https://github.com/blinkfox/hexo-theme-matery" target="_blank">Matery</a> -->
            <br>
            
                &nbsp;<i class="fas fa-chart-area"></i>&nbsp;站点总字数:&nbsp;<span
                        class="white-color">603.8k</span>
            
            
            
                
            
            
                <span id="busuanzi_container_site_pv">
                &nbsp;|&nbsp;<i class="far fa-eye"></i>&nbsp;总访问量:&nbsp;
                    <span id="busuanzi_value_site_pv" class="white-color"></span>
            </span>
            
            
                <span id="busuanzi_container_site_uv">
                &nbsp;|&nbsp;<i class="fas fa-users"></i>&nbsp;总访问人数:&nbsp;
                    <span id="busuanzi_value_site_uv" class="white-color"></span>
            </span>
            
            <br>

            <!-- 运行天数提醒. -->
            
                <span id="sitetime"> Loading ...</span>
                <script>
                    var calcSiteTime = function () {
                        var seconds = 1000;
                        var minutes = seconds * 60;
                        var hours = minutes * 60;
                        var days = hours * 24;
                        var years = days * 365;
                        var today = new Date();
                        var startYear = "2021";
                        var startMonth = "11";
                        var startDate = "12";
                        var startHour = "0";
                        var startMinute = "0";
                        var startSecond = "0";
                        var todayYear = today.getFullYear();
                        var todayMonth = today.getMonth() + 1;
                        var todayDate = today.getDate();
                        var todayHour = today.getHours();
                        var todayMinute = today.getMinutes();
                        var todaySecond = today.getSeconds();
                        var t1 = Date.UTC(startYear, startMonth, startDate, startHour, startMinute, startSecond);
                        var t2 = Date.UTC(todayYear, todayMonth, todayDate, todayHour, todayMinute, todaySecond);
                        var diff = t2 - t1;
                        var diffYears = Math.floor(diff / years);
                        var diffDays = Math.floor((diff / days) - diffYears * 365);

                        // 区分是否有年份.
                        var language = 'zh-CN';
                        if (startYear === String(todayYear)) {
                            document.getElementById("year").innerHTML = todayYear;
                            var daysTip = 'This site has been running for ' + diffDays + ' days';
                            if (language === 'zh-CN') {
                                daysTip = '本站已运行 ' + diffDays + ' 天';
                            } else if (language === 'zh-HK') {
                                daysTip = '本站已運行 ' + diffDays + ' 天';
                            }
                            document.getElementById("sitetime").innerHTML = daysTip;
                        } else {
                            document.getElementById("year").innerHTML = startYear + " - " + todayYear;
                            var yearsAndDaysTip = 'This site has been running for ' + diffYears + ' years and '
                                + diffDays + ' days';
                            if (language === 'zh-CN') {
                                yearsAndDaysTip = '本站已运行 ' + diffYears + ' 年 ' + diffDays + ' 天';
                            } else if (language === 'zh-HK') {
                                yearsAndDaysTip = '本站已運行 ' + diffYears + ' 年 ' + diffDays + ' 天';
                            }
                            document.getElementById("sitetime").innerHTML = yearsAndDaysTip;
                        }
                    }

                    calcSiteTime();
                </script>
            
            <br>
            
                <span id="icp"><img src="/medias/icp.png"
                                    style="vertical-align: text-bottom;"/>
                <a href="https://beian.miit.gov.cn" target="_blank">陕ICP备2021014294号-1</a>
            </span>
            
        </div>
        <div class="col s12 m4 l4 social-link social-statis">
    <a href="https://github.com/jackwang0108" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fab fa-github"></i>
    </a>



    <a href="mailto:2232123545@qq.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fas fa-envelope-open"></i>
    </a>







    <a href="tencent://AddContact/?fromId=50&fromSubId=1&subcmd=all&uin=2232123545" class="tooltipped" target="_blank" data-tooltip="QQ联系我: 2232123545" data-position="top" data-delay="50">
        <i class="fab fa-qq"></i>
    </a>







</div>
    </div>
</footer>

<div class="progress-bar"></div>


    <!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fas fa-search"></i>&nbsp;&nbsp;搜索</span>
            <input type="search" id="searchInput" name="s" placeholder="请输入搜索的关键字"
                   class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script type="text/javascript">
$(function () {
    var searchFunc = function (path, search_id, content_id) {
        'use strict';
        $.ajax({
            url: path,
            dataType: "xml",
            success: function (xmlResponse) {
                // get the contents from search data
                var datas = $("entry", xmlResponse).map(function () {
                    return {
                        title: $("title", this).text(),
                        content: $("content", this).text(),
                        url: $("url", this).text()
                    };
                }).get();
                var $input = document.getElementById(search_id);
                var $resultContent = document.getElementById(content_id);
                $input.addEventListener('input', function () {
                    var str = '<ul class=\"search-result-list\">';
                    var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                    $resultContent.innerHTML = "";
                    if (this.value.trim().length <= 0) {
                        return;
                    }
                    // perform local searching
                    datas.forEach(function (data) {
                        var isMatch = true;
                        var data_title = data.title.trim().toLowerCase();
                        var data_content = data.content.trim().replace(/<[^>]+>/g, "").toLowerCase();
                        var data_url = data.url;
                        data_url = data_url.indexOf('/') === 0 ? data.url : '/' + data_url;
                        var index_title = -1;
                        var index_content = -1;
                        var first_occur = -1;
                        // only match artiles with not empty titles and contents
                        if (data_title !== '' && data_content !== '') {
                            keywords.forEach(function (keyword, i) {
                                index_title = data_title.indexOf(keyword);
                                index_content = data_content.indexOf(keyword);
                                if (index_title < 0 && index_content < 0) {
                                    isMatch = false;
                                } else {
                                    if (index_content < 0) {
                                        index_content = 0;
                                    }
                                    if (i === 0) {
                                        first_occur = index_content;
                                    }
                                }
                            });
                        }
                        // show search results
                        if (isMatch) {
                            str += "<li><a href='" + data_url + "' class='search-result-title'>" + data_title + "</a>";
                            var content = data.content.trim().replace(/<[^>]+>/g, "");
                            if (first_occur >= 0) {
                                // cut out 100 characters
                                var start = first_occur - 20;
                                var end = first_occur + 80;
                                if (start < 0) {
                                    start = 0;
                                }
                                if (start === 0) {
                                    end = 100;
                                }
                                if (end > content.length) {
                                    end = content.length;
                                }
                                var match_content = content.substr(start, end);
                                // highlight all keywords
                                keywords.forEach(function (keyword) {
                                    var regS = new RegExp(keyword, "gi");
                                    match_content = match_content.replace(regS, "<em class=\"search-keyword\">" + keyword + "</em>");
                                });

                                str += "<p class=\"search-result\">" + match_content + "...</p>"
                            }
                            str += "</li>";
                        }
                    });
                    str += "</ul>";
                    $resultContent.innerHTML = str;
                });
            }
        });
    };

    searchFunc('/search.xml', 'searchInput', 'searchResult');
});
</script>

    <!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fas fa-arrow-up"></i>
    </a>
</div>


    <script src="/libs/materialize/materialize.min.js"></script>
    <script src="/libs/masonry/masonry.pkgd.min.js"></script>
    <script src="/libs/aos/aos.js"></script>
    <script src="/libs/scrollprogress/scrollProgress.min.js"></script>
    <script src="/libs/lightGallery/js/lightgallery-all.min.js"></script>
    <script src="/js/matery.js"></script>

    

    
        
        <script type="text/javascript">
            // 只在桌面版网页启用特效
            var windowWidth = $(window).width();
            if (windowWidth > 768) {
                document.write('<script type="text/javascript" src="/libs/others/sakura.js"><\/script>');
            }
        </script>
    

    <!-- 雪花特效 -->
    

    <!-- 鼠标星星特效 -->
    

     
        <script src="https://ssl.captcha.qq.com/TCaptcha.js"></script>
        <script src="/libs/others/TencentCaptcha.js"></script>
        <button id="TencentCaptcha" data-appid="xxxxxxxxxx" data-cbfn="callback" type="button" hidden></button>
    

    <!-- Baidu Analytics -->

    <!-- Baidu Push -->

<script>
    (function () {
        var bp = document.createElement('script');
        var curProtocol = window.location.protocol.split(':')[0];
        if (curProtocol === 'https') {
            bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
        } else {
            bp.src = 'http://push.zhanzhang.baidu.com/push.js';
        }
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(bp, s);
    })();
</script>

    
    <script src="/libs/others/clicklove.js" async="async"></script>
    
    
    <script async src="/libs/others/busuanzi.pure.mini.js"></script>
    

    

    

    <!--腾讯兔小巢-->
    
    

    

    

    
    <script src="/libs/instantpage/instantpage.js" type="module"></script>
    

</body>

</html>
